037 · Isomorphic Strings

algorithm
Published

June 15, 2026

My First Thoughts

看到这道题，第一反应还是需要字典。

s 中某个字符之前已经对应过 t 中哪个字符。

所以可以先写一个 mapping：

mapping = {}

for index in range(len(s)):
    key = s[index]
    value = t[index]

    if key in mapping:
        if mapping[key] != value:
            return False
    else:
        mapping[key] = value

return True

这是首先想到的，这满足了第一条规则：

同一个字符每次都必须替换成同一个字符。

比如：

s = "foo"
t = "bar"

第一次看到 "o" 的时候，记录的是：

o -> a

第二次再看到 "o"，它却想对应 "r"，这就和之前的记录冲突，所以可以返回 False。

但是题目还有第二条规则：

不同字符不能替换成同一个字符。

只靠当前这个 mapping 好像还不够。比如：

s = "ab"
t = "cc"

只看 s -> t 的映射，会得到：

a -> c
b -> c

"a" 自己一直对应 "c"，"b" 自己也一直对应 "c"，所以单向 mapping 不会发现问题。

真正的问题是："c" 已经被 "a" 用过了，不能再被 "b" 用。

所以可以再引入一个 used 字典，反过来记录 t 里的字符已经被哪个 s 字符占用了：

used = {}

if value in used:
    if used[value] != key:
        return False
else:
    used[value] = key

这样直接加到原来的检查后面，就能同时处理两个方向的限制。

Why That Is Not Enough

这次思路其实已经完全正确了，而且抓住了这道题的核心考点：同构不是单向关系，而是双向约束。

第一步想到 mapping，已经解决了：

同一个 s 字符不能对应到不同的 t 字符。

接着又意识到 mapping 还挡不住 s = "ab"、t = "cc"，于是补了一个反向的 used，这正好解决了：

不同的 s 字符不能对应到同一个 t 字符。

接下来只要把 mapping 和 used 两段检查放进同一个循环里。每次同时检查正向映射和反向占用，只要两个方向都没有冲突，就继续往后走。

Final Idea

保留原来的 mapping，再加一个反向字典 used。

两个字典分别负责不同的问题：

  • mapping[key] = value：记录 s 中的 key 应该变成 t 中的 value
  • used[value] = key：记录 t 中的 value 已经被 s 中的哪个 key 使用

遍历每一对字符 key = s[i]、value = t[i] 时，做两次检查：

  1. 如果 key 已经在 mapping 里，它必须仍然对应当前的 value
  2. 如果 value 已经在 used 里，它必须仍然来自当前的 key

只要有任意一个方向冲突，就返回 False。如果整条字符串都没有冲突，就返回 True。

Why It Works

同构字符串要求的是一种一对一的字符关系。

第一层要求是稳定：同一个 s 字符不能一会儿变成这个字符，一会儿变成另一个字符。mapping 正好负责检查这个。

第二层要求是不能合并：两个不同的 s 字符不能都变成同一个 t 字符。used 正好负责检查这个。

每次同时检查这两个方向，就等于保证了：

  • 从 s 到 t 没有冲突
  • 从 t 回看 s 也没有冲突

这两个条件都满足时，每个字符的替换关系就是一致且不重复的，所以两个字符串是同构的。

Code

def isIsomorphic(s, t):
    mapping = {}
    used = {}

    for key, value in zip(s, t):
        if key in mapping and mapping[key] != value:
            return False

        if value in used and used[value] != key:
            return False

        mapping[key] = value
        used[value] = key

    return True

Complexity

Time \(O(n)\) - n 是字符串长度；每一对字符只检查一次
Space \(O(1)\) - 题目限制字符来自 ASCII，最多记录固定数量的字符映射

Takeaway

当题目说“不同东西不能对应到同一个东西”时，只做正向映射通常不够。补一个反向映射，就能把“稳定对应”和“不能重复占用”这两个约束都表达清楚。

← Quiz