LeetCode 205. 同构字符串

约 5 分钟
文章信息 10 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 5-10 字节跳动 美团 阿里巴巴 百度 面试经典 150 题
标签
字符串 哈希表
目录

题目描述

✅ 205. 同构字符串

image-20230312172634032

题意分析

输入两个字符串 s 和 t，判断能否通过「把 s 里的每种字符统一换成另一种字符」得到 t，返回布尔值。

题目对替换规则有两条硬性要求：同一种字符每次出现都必须换成同一个结果，不能这次换成 a、下次换成 b；两种不同的字符不能换成同一个结果。前者要求映射是良定义的函数，后者要求它是单射，合起来就是「一一对应」。字符允许换成自己，所以恒等映射也是合法的。

注意判定是双向对称的：只检查 s 到 t 会漏掉「两个不同字符撞到同一个目标」的情形，反过来只检查 t 到 s 同样有漏。

约束里两串长度可达 $5 \times 10^4$，字符是任意 ASCII 字符（不局限于小写字母），所以计数容器要按 128 或 256 开，或者干脆用哈希表。边界上要覆盖：长度不同直接判否；空串与空串同构；两串完全相同时必然同构。

解法：双向映射

核心思路

同构要求字符一一对应，需要同时维护 s -> t 和 t -> s 两个方向：前者保证同一个源字符始终映射到同一个目标字符，后者防止两个不同源字符映射到同一个目标字符。只检查单向映射会把 s = "ab"、t = "cc" 误判为同构。

题目字符集是 ASCII，因此用两个长度为 128 的数组即可代替哈希表。数组默认值 0 表示尚未建立映射，实际字符编码存为 code + 1，避免 ASCII 码 0 与默认值冲突；如果字符范围不固定，应改用哈希表。

遍历中的不变量是：处理完下标 i 后，两个数组准确记录前缀 0..i 的双向映射。遇到任一方向与已有记录冲突时，一一对应不可能成立；若整串都无冲突，两张表共同证明映射既一致又不重复。

解题步骤

  1. 长度不同直接返回 false。
  2. 创建 sToT、tToS 两个映射数组。
  3. 逐位读取字符 a = s[i]、b = t[i]：若 a 已映射但目标不是 b，或 b 已被映射但来源不是 a，立即返回 false。
  4. 将 a -> b、b -> a 同步写入两个数组。
  5. 遍历结束仍无冲突，返回 true。

例如 egg 与 add 会稳定建立 e -> a、g -> d；而 ab 与 cc 在第二位触发反向冲突，因为 c 已经对应 a，不能再对应 b。

代码实现

class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }

        int[] sToT = new int[128];
        int[] tToS = new int[128];
        for (int i = 0; i < s.length(); i++) {
            int a = s.charAt(i);
            int b = t.charAt(i);
            if ((sToT[a] != 0 && sToT[a] != b + 1)
                    || (tToS[b] != 0 && tToS[b] != a + 1)) {
                return false;
            }
            sToT[a] = b + 1;
            tToS[b] = a + 1;
        }
        return true;
    }
}

func isIsomorphic(s string, t string) bool {
    if len(s) != len(t) {
        return false
    }

    var sToT, tToS [128]int
    for i := 0; i < len(s); i++ {
        a := s[i]
        b := t[i]
        if (sToT[a] != 0 && sToT[a] != int(b)+1) ||
            (tToS[b] != 0 && tToS[b] != int(a)+1) {
            return false
        }
        sToT[a] = int(b) + 1
        tToS[b] = int(a) + 1
    }
    return true
}

复杂度分析

  • 时间复杂度：$O(n)$，其中 n 是字符串长度，每个位置只检查一次。
  • 空间复杂度：$O(1)$，两个数组大小由固定的 ASCII 字符集决定。

关键点总结

  • 双向映射分别保证“一个源只有一个目标”和“一个目标只有一个来源”。
  • 两个方向必须在同一轮同步检查、同步更新，前缀不变量才成立。
  • code + 1 让 0 安全地表示未映射，包括 ASCII 码为 0 的字符。
  • 定长数组依赖 ASCII 约束；若输入可能包含更大的字符集，应改用哈希表。

易错点总结

  • 只检查 s -> t：ab 与 cc 会被误判为同构，必须检查反向占用。
  • 数组只按 26 个小写字母开：题目还允许大写字母、数字和符号。
  • 直接用 0 保存字符编码：无法区分“映射到 ASCII 码 0”和“尚未映射”，应统一加一。
  • 忘记先比较长度：可能越界，或错误接受只有公共前缀相同的字符串。
  • 把字符频次相同当成同构：频次无法表达逐位置的一一对应关系。

相似题目

题目 难度 考察点
290. 单词规律 简单 映射的一端是单词而非字符，需要先切分再双向校验
242. 有效的字母异位词 简单 只看字符频次是否相同，与位置顺序无关
49. 字母异位词分组 中等 要为每组构造规范化的哈希键并聚合
383. 赎金信 简单 判定的是频次的包含关系而非相等
1002. 查找共用字符 简单 多串频次取最小值，输出交集而非布尔判定
1657. 确定两个字符串是否接近 中等 允许频次整体重排，判定条件放宽为频次多重集合相同