原题
给定两个字符串 s 和 t，判断它们是否是同构的。
如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。
所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。
示例1：
输入： s = "egg", t = "add"
输出： true
示例2：
输入： s = "foo", t = "bar"
输出： false
示例3：
输入： s = "paper", t = "title"
输出： true
解法
思想
- 相同的字符要对应相同的字符，那么相同字符处于后位置的字符的第一次出现的位置就应该相同。
- 哈希表记录对应关系
代码
- indexOf （作者:hao-fei-hao）
class Solution {
public boolean isIsomorphic(String s, String t) {
char[] ch1 = s.toCharArray();
char[] ch2 = t.toCharArray();
int len = s.length();
for (int i = 0; i < len; i++) {
if(s.indexOf(ch1[i]) != t.indexOf(ch2[i])){
return false;
}
}
return true;
}
}
- 哈希表
class Solution {
public boolean isIsomorphic(String s, String t) {
Map<Character,Character> map = new HashMap<>();
Map<Character,Character> mapB = new HashMap<>();
for(int i = 0;i<s.length();i++){
if(map.containsKey(s.charAt(i))){
if(t.charAt(i)!=map.get(s.charAt(i))) return false;
}
if(mapB.containsKey(t.charAt(i))){
if(s.charAt(i)!=mapB.get(t.charAt(i))) return false;
}
map.put(s.charAt(i),t.charAt(i));
mapB.put(t.charAt(i),s.charAt(i));
}
return true;
}
}
或
class Solution {
public boolean isIsomorphic(String s, String t) {
HashMap<Character,Character> map=new HashMap<>();
for (int i=0;i<s.length();i++){
if (map.containsKey(s.charAt(i))) {
if (map.get(s.charAt(i))!=t.charAt(i)) return false;
}else{
//不存在对应的键但是存在对应的值
if (map.containsValue(t.charAt(i))) return false;
else map.put(s.charAt(i),t.charAt(i));
}
}
return true;
}
}
- 抽象一个模式字符串来匹配
func isIsomorphic(s string, t string) bool {
return patternStr(s) == patternStr(t)
}
func patternStr(s string) string{
letterCount := map[byte]int{}
count := 1
res := ""
for _, c := range []byte(s){
thisCount := letterCount[c]
if thisCount == 0{
letterCount[c] = count
thisCount = count
}
res += strconv.Itoa(thisCount)
count ++
}
return res
}
相似题
https://leetcode.cn/problems/word-pattern/description/
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode205-%e5%90%8c%e6%9e%84%e5%ad%97%e7%ac%a6%e4%b8%b2/
