题目:
给定两个字符串 s 和 t ,判断它们是否是同构的。
如果 s 中的字符可以按某种映射关系替换得到 t ,那么这两个字符串是同构的。
每个出现的字符都应当映射到另一个字符,同时不改变字符的顺序。不同字符不能映射到同一个字符上,相同字符只能映射到同一个字符上,字符可以映射到自己本身。
示例 1:
输入:s = "egg", t = "add"
输出:true
示例 2:
输入:s = "foo", t = "bar"
输出:false
示例 3:
输入:s = "paper", t = "title"
输出:true
提示:
1 <= s.length <= 5 * 104
t.length == s.length
s 和 t 由任意有效的 ASCII 字符组成
首先我们来分析这个题目的要求是什么,当然这一块看起来像是在做语文题。不过在我们的实际生活和工作中,善于与人沟通也是一个很重要的技能嘛。
egg add, 这两个字符串如果把左边的e改为a,g改为d就可以完美的将add改为egg。这就说明add和egg是同构字符串;左边的每一个字符都只能有一个替代者。
那么我们很容易可以想到哈希表可以让我们对字符串中的每一个字符都有一个固定的映射。
现在我们知道了,我们需要2个哈希表。
Map<Character, Character> s2t = new HashMap<Character,Character>();
Map<Character, Character> t2s = new HashMap<Character,Character>();
在两个哈希表中,哈希值为另一个字符串的字符,存储的元素为本字符串的字符。也就是说,S字符串的字符存储在s2t这个哈希表中,s的字符存进的位置的编号为t的对应位置的字符。这样我们只需要判断,每一次存储进对应的字符时,之前有没有出现过不一样的对应值。
完整代码
class Solution {
public boolean isIsomorphic(String s, String t) {
Map<Character, Character> s2t = new HashMap<Character,Character>();
Map<Character, Character> t2s = new HashMap<Character,Character>();
int len = s.length();
for(int i=0;i<len;++i){
char x = s.charAt(i), y = t.charAt(i); //获取s和t在 i 位置的字符,并存储进x和y
if((s2t.containsKey(x) && s2t.get(x) != y) || (t2s.containsKey(y) && t2s.get(y) != x)){ //双向验证,只要有一边的字符对不上另一边的字符便返回false
return false;
}
s2t.put(x,y);
t2s.put(y,x);
}
return true;
}
}
标签:字符,同构,HashMap,映射,哈希,字符串
From: https://www.cnblogs.com/Radioactive/p/18221209