同构字符串 图解题解

这道题到底在问什么

s

"cbaabc"

t

"zyxxyz"

输出

true

最优解：一步一步想明白

1. 3核心是一张 s→t 的映射表，再加一条铁律：映射必须双向一对一——同一个 s 字符只能对一个 t 字符，同一个 t 字符也只能被一个 s 字符占用。
2. 4开始前：s→t 的映射表是空的。下面把 s 的字符放在格子里，t 的对应字符列在下方，一位一位地对齐检查。
3. 5看第 0 位：s 这一格是 'c'（橙色），它在 t 里对应的字符是 'z'。下一步去映射表里查 'c' 之前记成了什么。
4. 6'c' 之前没出现过，就把它记进映射表：'c' → 'z'（绿色新增）。同时占用 t 字符 'z'，以后别的字母不能再映到它。
5. 7到这里前 1 位都对得上，映射表里每个 s 字符对一个 t 字符、每个 t 字符也只被一个 s 字符占用，没有冲突。继续。
6. 8看第 1 位：s 这一格是 'b'（橙色），它在 t 里对应的字符是 'y'。下一步去映射表里查 'b' 之前记成了什么。
7. 9'b' 之前没出现过，就把它记进映射表：'b' → 'y'（绿色新增）。同时占用 t 字符 'y'，以后别的字母不能再映到它。
8. 10到这里前 2 位都对得上，映射表里每个 s 字符对一个 t 字符、每个 t 字符也只被一个 s 字符占用，没有冲突。继续。
9. 11看第 2 位：s 这一格是 'a'（橙色），它在 t 里对应的字符是 'x'。下一步去映射表里查 'a' 之前记成了什么。
10. 12'a' 之前没出现过，就把它记进映射表：'a' → 'x'（绿色新增）。同时占用 t 字符 'x'，以后别的字母不能再映到它。
11. 13到这里前 3 位都对得上，映射表里每个 s 字符对一个 t 字符、每个 t 字符也只被一个 s 字符占用，没有冲突。继续。
12. 14看第 3 位：s 这一格是 'a'（橙色），它在 t 里对应的字符是 'x'。下一步去映射表里查 'a' 之前记成了什么。
13. 15'a' 之前记过，映到 'x'；这次它对的还是 'x'，前后一致（命中高亮），通过，继续下一位。
14. 16到这里前 4 位都对得上，映射表里每个 s 字符对一个 t 字符、每个 t 字符也只被一个 s 字符占用，没有冲突。继续。
15. 17看第 4 位：s 这一格是 'b'（橙色），它在 t 里对应的字符是 'y'。下一步去映射表里查 'b' 之前记成了什么。
16. 18'b' 之前记过，映到 'y'；这次它对的还是 'y'，前后一致（命中高亮），通过，继续下一位。
17. 19到这里前 5 位都对得上，映射表里每个 s 字符对一个 t 字符、每个 t 字符也只被一个 s 字符占用，没有冲突。继续。
18. 20看第 5 位：s 这一格是 'c'（橙色），它在 t 里对应的字符是 'z'。下一步去映射表里查 'c' 之前记成了什么。
19. 21'c' 之前记过，映到 'z'；这次它对的还是 'z'，前后一致（命中高亮），通过，继续下一位。
20. 22到这里前 6 位都对得上，映射表里每个 s 字符对一个 t 字符、每个 t 字符也只被一个 s 字符占用，没有冲突。继续。
21. 23整串对齐完毕：c↔z、b↔y、a↔x 从头到尾都一致，也没有两个字母撞到同一个目标。s 和 t 同构，返回 true。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

def isIsomorphic(s, t):
    st, ts = {}, {}                    # s→t 和 t→s 两张映射表
    for a, b in zip(s, t):
        if a in st and st[a] != b:     # s 字符映出两种结果
            return False
        if b in ts and ts[b] != a:     # 两个 s 字符撞同一个 t 字符
            return False
        st[a], ts[b] = b, a            # 记下双向映射
    return True

bool isIsomorphic(string s, string t){
    unordered_map<char,char> st, ts;
    for (int i = 0; i < s.size(); i++) {
        char a = s[i], b = t[i];
        if (st.count(a) && st[a] != b) return false;
        if (ts.count(b) && ts[b] != a) return false;
        st[a] = b; ts[b] = a;
    }
    return true;
}

public boolean isIsomorphic(String s, String t) {
    Map<Character,Character> st = new HashMap<>(), ts = new HashMap<>();
    for (int i = 0; i < s.length(); i++) {
        char a = s.charAt(i), b = t.charAt(i);
        if (st.containsKey(a) && st.get(a) != b) return false;
        if (ts.containsKey(b) && ts.get(b) != a) return false;
        st.put(a, b); ts.put(b, a);
    }
    return true;
}

复杂度

面试官可能追问