§1
题目描述
给定两个字符串 s 和 t,判断它们是否是同构的。如果 s 中的字符可以按某种映射关系替换得到 t,那么这两个字符串是同构的。每个出现的字符都应当映射到另一个字符,不改变字符顺序;不同字符不能映射到同一个字符上,相同字符只能映射到同一个字符上,字符可以映射到自己本身。
输入 = s = "egg", t = "add"
输出 = true
输入 = s = "f11", t = "b23"
输出 = false
输入 = s = "paper", t = "title"
输出 = true
§2
思路解析动画文字版
单向映射只能保证“一个 s 字符不分裂成多个 t 字符”,不能保证“多个 s 字符不挤到同一个 t 字符”。
不变量:st 和 ts 始终互相吻合,表示目前读过的字符仍然是一一对应关系。
长度检查:paper 和 title 都是 5:同构必须逐字符一一对应。长度不同直接 false;这里两个字符串长度相同,继续建立双向映射。
初始化:两张映射表都为空:st 负责检查同一个 s 字符是否稳定;ts 负责检查同一个 t 字符是否只被一个 s 字符使用。
读 p -> t:检查通过并记录:p 还没有映射,t 也没有被占用,所以这一对可以接受。记录两个方向:以后再见 p,必须还是 t;以后再见 t,必须还是 p。
读 a -> i:新增第二组映射:a 和 i 也都没冲突,加入两张表。当前映射是 p->t、a->i。
读 p -> t:旧映射一致:第三对又是 p->t。两张表都能对上,说明重复字符保持了同样的映射。
读 e -> l:继续新增:e 和 l 都是新字符,加入映射表。
读 r -> e:新增最后一组:这里 t 中的 e 和 s 中的 e 是不同位置、不同方向的字符,不冲突。双向表只要求同一方向内保持一一对应。
扫描结束:没有冲突,返回 true:所有字符对都通过双向检查,所以 paper 和 title 同构。
同构字符串、单词规律、模式匹配,都常用这套双向表检查。
§3
参考代码
class Solution: def isIsomorphic(self, s, t): 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看懂代码不等于写得出。盖住上面,自己默写一遍试试。卡在哪一行说不清,就点右下角问小欧。
§4
复杂度
- 时间复杂度:O(n),同时扫描 s 和 t 一遍。
- 空间复杂度:O(1),题目限制为 ASCII 字符,映射表大小有常数上界;若按一般字符集可记为 O(n)。
§5
易错点
✗ 错误写法:只检查 s -> t
✓ 正确写法:同时检查 t -> s
ab -> cc 会被单向映射误判为 true。
✗ 错误写法:看到同名字符就直接判冲突
✓ 正确写法:按方向看映射关系
paper -> title 中,s 的 e 和 t 的 e 出现在不同映射方向,不冲突。
✗ 错误写法:长度不同仍继续扫描
✓ 正确写法:长度不同直接 false
无法逐字符一一对应。
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
下一题 · 哈希套路 2/8
→存在重复元素
LeetCode 217 · 简单 · 沿着 哈希套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
299道动画图解
37节语音讲解
28课数据结构
¥0.27折合 / 天
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
¥99 开通年卡 →
想成体系刷透这类套路?去图解算法专题