LeetCode 205. 同构字符串

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

题目描述

✅ 205. 同构字符串

image-20260928235504899

image-20260928235504900

题意分析

要在不改变字符位置的前提下，把 s 中的字符统一替换成 t 中对应的字符。同一个来源字符必须始终换成同一个目标字符，不同来源字符也不能换成同一个目标字符；映射到自身是允许的。

每个位置都给出一对必须成立的映射。扫描时既要检查来源是否改换目标，也要检查目标是否已被其他来源占用，因此分别保存 s -> t 和 t -> s 两个方向的对应关系。

解法：双向映射

核心思路

[!blue]

sToT[a] 记录来源字符 a 应映射到谁，保证同一个字符的替换结果一致；tToS[b] 记录目标字符 b 已被谁占用，保证两个不同来源不会合并成同一个目标。只记录第一个方向无法发现目标被重复占用。

题目限定 ASCII 字符，编码范围为 0 到 127，所以用长度为 128 的数组就能表示映射。数组初始值 0 表示尚未记录；实际保存字符编码加一，避免映射到编码为零的字符时与未记录状态混淆。Java 读取到的字符编码和 Go 读取到的字节值，都可以直接作为数组下标。

每轮读取 a = s[i]、b = t[i]，先检查两个已有记录：若 a 的目标不是 b，或 b 的来源不是 a，当前配对与前缀冲突，立即返回 false。没有冲突时，再写入 sToT[a] = b+1 和 tToS[b] = a+1；已有的同一配对重复写入不影响结果。

扫描开始时映射为空；每一轮都只补充相容的一对映射，所以处理完的前缀始终满足一一对应。若出现冲突，任何统一替换方案都无法同时满足前后两个位置；若扫描结束仍无冲突，记录的映射就能逐位将整个 s 替换成 t，因此返回 true。

解题步骤

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

代码实现

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 字符集决定。

关键点总结

[!green]

  • 双向映射分别保证“一个源只有一个目标”和“一个目标只有一个来源”。
  • 两个方向必须在同一轮同步检查、同步更新，前缀不变量才成立。
  • code + 1 让 0 安全地表示未映射，包括 ASCII 码为 0 的字符。

易错点总结

[!yellow]

  • 只检查 s -> t 会允许多个来源共享一个目标，必须检查反向占用。
  • 数组只按 26 个小写字母开：题目还允许大写字母、数字和符号。
  • 直接用 0 保存字符编码：无法区分“映射到 ASCII 码 0”和“尚未映射”，应统一加一。
  • 忘记先比较长度：可能越界，或错误接受只有公共前缀相同的字符串。
  • 把字符频次相同当成同构：频次无法表达逐位置的一一对应关系。
  • 先覆盖旧映射再判断，会丢失冲突证据；应先核对，再更新。字符映射到自身也按同一套规则处理，不需要排除。

相似题目

题目 难度 关联与区别
290. 单词规律 简单 同样要求双向一一映射，原题把模式字符映射到单词，本题映射到另一个字符。
890. 查找和替换模式 中等 同样按字符首次出现模式检查一一对应，原题从词表中筛出所有同构单词。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/39186524
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！