[面试题] 字符串同构算法解析：Python 双映射解法与面试避坑指南

昨天还在群里哀嚎“没对象，活得没意思”，今天一觉醒来，工位都快没了，这剧情真比相亲市场还狠。

找对象这事，起码还能嘴硬说一句“缘分没到”。工作可不跟你讲缘分，优化名单一发，连装淡定的机会都不给。网友说得挺损：对象没找到，倒先被社会收编了。还有人补刀，说成年人的感情问题，最后都会拐到钱上，这话难听，但真不算瞎说。

你细想也挺扎心。以前大家催你恋爱，现在都没空催了，先看看这个月工资还发不发。没对象最多是下班回家安静点，没工作那是真睡都睡不踏实，HR一个电话过来，眼皮都得跳一下。

所以现在看人喊单身，我都没啥感觉了。先别急着愁桃花，保住饭碗再说。

算法题：找出变位映射

字符串一长，很多人第一反应就是排序。

sorted(a) == sorted(b) 能不能做？能。面试里也能过一批题。但这写法我一般只当保底，不当首选。原因很简单：你明明只是在判断两个串是不是同一批字符的重排，结果先把两边都排了一遍，手法有点重。

“找出变位映射”这类题，核心不是排顺序，是看每个字符出现的位置关系能不能一一对上。 比如：

• egg -> add，e 一直映射 a，g 一直映射 d，这就成立。
• foo -> bar，o 前后两次，结果一个映到 a 一个映到 r，直接穿帮。

这种题我通常先看两个方向：

1. s[i] -> t[i] 不能变来变去
2. t[i] -> s[i] 也不能一对多

少看一边，十有八九会漏。

先看个最直接的写法，两个哈希表就够了：

def is_isomorphic(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False

    st = {}
    ts = {}

    for a, b in zip(s, t):
        if a in st and st[a] != b:
            return False
        if b in ts and ts[b] != a:
            return False

        st[a] = b
        ts[b] = a

    return True

拿几组数据试一下：

print(is_isomorphic("egg", "add"))    # True
print(is_isomorphic("foo", "bar"))    # False
print(is_isomorphic("paper", "title"))  # True
print(is_isomorphic("ab", "aa"))      # False

这题不难，坑主要在“自以为一个字典就够了”。

比如有人会这么写：

def bad_case(s: str, t: str) -> bool:
    mp = {}
    for a, b in zip(s, t):
        if a in mp and mp[a] != b:
            return False
        mp[a] = b
    return True

这段代码看着没毛病，实际有坑。“ab” 和 “aa” 会被判成 True。因为它只校验了左边到右边，没校验右边是不是被两个字符同时占用了。

还有一种写法也挺顺手，不显式存映射，而是存“首次出现的位置模式”：

def encode_pattern(text: str) -> list[int]:
    pos = {}
    res = []

    for i, ch in enumerate(text):
        if ch not in pos:
            pos[ch] = i
        res.append(pos[ch])

    return res

def is_isomorphic_v2(s: str, t: str) -> bool:
    return encode_pattern(s) == encode_pattern(t)

比如：

• paper -> [0,1,0,3,4]
• title -> [0,1,0,3,4]

模式一样，就说明映射关系一致。

真到面试里，我更愿意写第一种。原因不是它更短，而是排查最方便。哪个字符冲突、哪一步冲突，一眼就能打日志看出来。算法题写到最后，别只顾着“过题”，代码最好也像线上排问题那样，出了错知道先看哪。想要探讨更多类似的算法题或面试技巧，欢迎来我们云栈社区逛逛。