实战：同构字符串 ​

"egg" 和 "add" 是同构的吗？"foo" 和 "bar" 呢？

首先要问一个问题：什么是"同构"？

题目描述 ​

LeetCode 205. 同构字符串

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

如果 s 中的字符可以按某种映射关系替换得到 t，那么这两个字符串是同构的。

规则：

• 每个字符都应映射到另一个字符
• 不同字符不能映射到同一个字符
• 相同字符只能映射到同一个字符
• 字符可以映射到自己

示例：

输入：s = "egg", t = "add"
输出：true
解释：'e' -> 'a', 'g' -> 'd'

输入：s = "foo", t = "bar"
输出：false
解释：'o' 需要同时映射到 'a' 和 'r'，矛盾

输入：s = "paper", t = "title"
输出：true
解释：'p' -> 't', 'a' -> 'i', 'e' -> 'l', 'r' -> 'e'

核心理解 ​

现在我要问第二个问题：为什么 "foo" 和 "bar" 不是同构的？

分析一下：

• f[0] = 'f', t[0] = 'b' → 建立映射 'f' -> 'b'
• s[1] = 'o', t[1] = 'a' → 建立映射 'o' -> 'a'
• s[2] = 'o', t[2] = 'r' → 'o' 已经映射到 'a'，现在又要映射到 'r'，矛盾！

所以关键是：相同字符必须映射到相同字符（一致性）。

但这还不够。思考一下：s = "ab", t = "aa" 是同构的吗？

按上面的逻辑：

• 'a' -> 'a' ✓
• 'b' -> 'a' ✓

看起来没问题？但其实错了！因为 'a' 和 'b' 这两个不同字符都映射到了 'a'，违反了"不同字符不能映射到同一个字符"的规则。

所以我们需要双向映射：不仅检查 s→t，还要检查 t→s。

解法：双向映射 ​

function isIsomorphic(s, t) {
    if (s.length !== t.length) return false;
    
    const s2t = new Map();  // s 到 t 的映射
    const t2s = new Map();  // t 到 s 的映射
    
    for (let i = 0; i < s.length; i++) {
        const cs = s[i];  // s 的当前字符
        const ct = t[i];  // t 的当前字符
        
        // 检查 s→t 映射的一致性
        if (s2t.has(cs) && s2t.get(cs) !== ct) {
            return false;  // 已有映射且不一致
        }
        
        // 检查 t→s 映射的一致性（防止不同字符映射到同一个）
        if (t2s.has(ct) && t2s.get(ct) !== cs) {
            return false;
        }
        
        // 建立双向映射
        s2t.set(cs, ct);
        t2s.set(ct, cs);
    }
    
    return true;
}

执行过程追踪 ​

以 s = "foo", t = "bar" 为例：

初始：s2t = {}, t2s = {}

i=0: cs='f', ct='b'
     s2t 没有 'f'，t2s 没有 'b'
     建立映射：s2t={'f':'b'}, t2s={'b':'f'}

i=1: cs='o', ct='a'
     s2t 没有 'o'，t2s 没有 'a'
     建立映射：s2t={'f':'b','o':'a'}, t2s={'b':'f','a':'o'}

i=2: cs='o', ct='r'
     s2t.get('o') = 'a' ≠ 'r'
     返回 false ❌

再看 s = "ab", t = "aa"：

i=0: cs='a', ct='a'
     建立映射：s2t={'a':'a'}, t2s={'a':'a'}

i=1: cs='b', ct='a'
     s2t 没有 'b' ✓
     但 t2s.get('a') = 'a' ≠ 'b' ❌
     返回 false

有没有发现？如果只做单向映射，"ab" 和 "aa" 会被误判为同构。双向映射正是为了防止这种情况。

复杂度分析 ​

• 时间复杂度：O(n)，遍历一次
• 空间复杂度：O(k)，k 是字符集大小

解法二：首次出现位置比较 ​

另一个思路：如果两个字符串同构，那么对应位置的字符首次出现的位置应该相同。

function isIsomorphic(s, t) {
    for (let i = 0; i < s.length; i++) {
        if (s.indexOf(s[i]) !== t.indexOf(t[i])) {
            return false;
        }
    }
    return true;
}

原理：

• s = "egg", t = "add"

• s[0]='e', 首次出现位置 0；t[0]='a', 首次出现位置 0 ✓

• s[1]='g', 首次出现位置 1；t[1]='d', 首次出现位置 1 ✓

• s[2]='g', 首次出现位置 1；t[2]='d', 首次出现位置 1 ✓

• s = "foo", t = "bar"

• s[2]='o', 首次出现位置 1；t[2]='r', 首次出现位置 2 ❌

代码简洁，但 indexOf 是 O(n)，总时间复杂度 O(n²)。

两种方法对比 ​

面试中建议用双向映射，展示对问题的深入理解。

常见错误 ​

1. 只做单向映射：会漏掉"不同字符映射到同一字符"的情况
2. 忘记检查长度：长度不同必定不同构
3. 混淆异位词和同构：异位词是字符频率相同，同构是映射关系一致，两个概念不同

相关题目 ​

• 290. 单词规律：判断字符串是否符合给定模式，同构思想
• 205. 同构字符串：本题
• 49. 字母异位词分组：基于字符映射的分组问题

本章小结 ​

同构字符串的核心是双向映射：

• s→t：相同字符必须映射到相同字符
• t→s：不同字符不能映射到同一字符

这道题和"有效的字母异位词"看起来类似，但考查的是完全不同的概念。异位词关注字符频率，同构关注映射关系。

字符串基础部分到此结束。下一部分，我们将进入字符串匹配算法的学习——包括 KMP、Rabin-Karp 等经典算法。