205. 同构字符串

Posted on | In
Words count in article: 406 | Reading time ≈ 1

题目

给定两个字符串 s 和 t，判断它们是否是同构的。

如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。

所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。

示例1：

1
2
输入: s = "egg", t = "add"
输出: true

示例2：

1
2
输入: s = "foo", t = "bar"
输出: false

示例3：

1
2
输入: s = "paper", t = "title"
输出: true

提示：

  • 1 <= s.length <= 5 * 104
  • t.length == s.length
  • s 和 t 由任意有效的 ASCII 字符组成

说明:

你可以假设 s 和 t 具有相同的长度。

解法

解法一：

遍历一次字符串，使用HashMap保存之前的映射关系。

以s在i位置上的字符c为key，t在i位置上的字符c1为value。

在遍历的过程中判断：

  1. 如果s中的当前字符c没有在map中，但是t的当前字符c1已经在map中了，说明c对应的字符c1已经被映射过一次了，返回false
  2. 如果s中的当前字符c在map中，则判断它们的映射字符是不是相等，不相等，返回false

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean isIsomorphic(String s, String t) {
		if (s.length() != t.length()) {
			return false;
		}
		HashMap<Character, Character> map = new HashMap<>();
		for (int i = 0; i < s.length(); i++) {
			char sc = s.charAt(i);
			char tc = t.charAt(i);
			if (!map.containsKey(sc)) {
				if (map.containsValue(tc)) {
					return false;
				}
				map.put(sc, tc);
			} else if (map.get(sc) != tc) {
				return false;
			}
		}
		return true;
	}
0%