力扣205-同构字符串
一、原题题目
1.1 题目
给定两个字符串 s
和 t
,判断它们是否是同构的。如果 s
中的字符可以按某种映射关系替换得到 t
,那么这两个字符串是同构的。每个出现的字符都应当映射到另一个字符,同时不改变字符的顺序。不同字符不能映射到同一个字符上,相同字符只能映射到同一个字符上,字符可以映射到自己本身。
1.2 示例
示例1:
输入:
s = "egg", t = "add"
输出:true
示例2:
输入:
s = "foo", t = "bar"
输出:false
示例3:
输入:
s = "paper", t = "title"
输出:true
提示:
- 可以假设
s
和t
长度相同。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/isomorphic-strings/
二、解题思路
2.1 利用【哈希表映射】解题
- 解题思路
这个题比较简单,简单思考想到用哈希表来存储映射关系,用 s 中的字符作为键, t 当中对应位置的字符作为值存储,当碰到下列两种情况需要返回 false 。否则将映射加入哈希表,直到遍历完字符串返回 true 。
1.当遍历到键在哈希表中已经存在但值与 t 中对应的值不同时则返回 false 。
2.当遍历到键不在哈希表中,但 t 中对应的值在哈希表中时也要返回 false 。
- 详细代码(Java)
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++){
if (map.containsKey(s.charAt(i)) && map.get(s.charAt(i))!=t.charAt(i))
return false; // 上述第一种情况
if (!map.containsKey(s.charAt(i)) && map.containsValue(t.charAt(i)))
return false; // 上述第二种情况
else map.put(s.charAt(i),t.charAt(i));
}
return true;
}
- 代码执行结果

2.2 利用【数组映射】解题
- 解题思路
相同上面利用哈希表的思路,这里换做用数组来保存映射关系。
- 详细代码(Java)
public boolean isIsomorphic(String s, String t) {
int[] sTt = new int[256]; // 保存 s 到 t 的映射
Arrays.fill(sTt, -1); // 初试都填充为-1
int[] tTs = new int[256]; // 保存 s 到 t 的映射
Arrays.fill(tTs, -1); // 初试都填充为-1
for (int i = 0;i<s.length();i++){
if (sTt[s.charAt(i)]!=-1&&sTt[s.charAt(i)]!=(int)(t.charAt(i)))
return false; // !=-1表示已经保存过当前位置元素S到t的映射,但是保存的值与当前t中当前位置值不一样
if (tTs[t.charAt(i)]!=-1&&tTs[t.charAt(i)]!=(int)(s.charAt(i)))
return false; // !=-1表示已经保存过当前位置元素t到s的映射,但是保存的值与当前s中当前位置值不一样
sTt[s.charAt(i)] = (int)(t.charAt(i)); // 没保存过,保存s到t的映射
tTs[t.charAt(i)] = (int)(s.charAt(i)); // 同时保存t到s的映射
}
return true;
}
- 代码执行结果

2.3 利用【数组连边】解题
- 解题思路
还是定义两个数组,为具有对应关系的字符连边并赋予权值,初始值为 0 表示未有映射关系,同为 0 才能连边。
- 详细代码(Java)
public boolean isIsomorphic(String s, String t) {
int[] sm = new int[256];
int[] tm = new int[256];
for (int i = 0;i<s.length();i++){
if (sm[s.charAt(i)]!=tm[t.charAt(i)])
return false;
sm[s.charAt(i)] = tm[t.charAt(i)] = i+1; // 连边符权值
}
return true;
}
- 代码执行结果
