刷 LeetCode 的朋友应该对这道题不陌生LeetCode 242 有效的字母异位词在“热门 100 题”里属于“新手村”级别的入门题地位类似于算法界的“Hello World”。但它远没有看上去那么简单——我在面试候选人的时候几乎每次都会拿这道题做热身能把这题答好的人后面难题往往也聊得比较顺。反过来如果连这题的坑都踩不明白那后面基本可以提前结束了。这道题表面上只问“两个单词的字母能不能重新排列成彼此”实际上考察的是三件事你对哈希表底层原理的理解、你对空间复杂度的敏感度以及你能不能把“熟题”讲出新意。所以这篇就系统地拆一遍从最无脑的排序解法开始一路优化到最优解再把时空复杂度掰开揉碎地讲清楚顺带附上面试和刷题过程中真正会遇到的坑。适合准备面试的朋友也适合刚接触 LeetCode 想建立“解题方法论”的同学。1. 题目解读与两种直觉思路1.1 题目到底在问什么先看题目本身给定两个字符串s和t写一个函数来判断t是否是s的字母异位词。所谓“字母异位词”翻译成人话就是——两个单词包含的字母种类一样每种字母的数量也一样只是排列顺序不同。经典例子就是anagram和nagaram字母全是 a、n、g、r、m 各一个只是顺序乱了而已。而rat和car就不是r 和 a 都有但 t 换成 c字符种类都不一样了自然不可能是异位词。这里有个容易被新手忽略的边界条件题目默认输入字符串只包含小写字母。这个限制很关键它直接影响我们后面选择什么数据结构。如果题目没这个限制比如输入可能包含大写字母、数字、甚至中文字符那解法就要升级这个我在后面“进阶场景”部分会专门讲。另外一个容易忽略的点是空字符串。s t 这两个算不算异位词按定义空串不包含任何字母字母种类和数量都是 0应该算 true。这个边界在代码里其实天然成立因为后面不管用哪种解法遍历完长度为 0 的字符串后统计结果都是全 0。1.2 思路一排序后逐一比较新手最直觉的想法是什么既然异位词只是顺序不同那我把两个字符串都排个序如果排序后完全相等那它们包含的字符集合和数量必然一致对吧这个思路完全正确代码也极短def isAnagram(s: str, t: str) - bool: return sorted(s) sorted(t)这写法能跑一道简单题嘛怎么都能过。但我强烈不建议你在实际面试里直接甩出这一版就结束。原因很简单排序的时间复杂度是 O(n log n)而这道题明明可以用 O(n) 解决。对于 n 是 10 万级别的输入两种解法的时间差距是很可观的。而且这里还有个隐蔽的坑不同的语言对字符串排序的实现细节不同。Python 的sorted(s)会生成一个新的字符数组再排序空间复杂度是 O(n)Java 里toCharArray()也会生成新数组。所以排序法看着代码简洁实际隐含了 O(n) 的额外空间不是理论上最优的方案。但这版代码也不是毫无价值。它作为“暴力解法”用于和最优解形成对比反而能帮你向面试官展示你的优化意识。当你先说“最自然的思路是排序但排序引入了 O(n log n) 的时间开销”然后再给出 O(n) 的哈希表解法时对方会觉得你脑子里有复杂度这根弦而不是只会背答案。1.3 思路二哈希表统计字符频次异位词的本质是字母频次相同。既然我们只关心“每个字母出现了几次”那就用一个字典哈希表把s里每个字符出现的次数记下来再用t去逐个核销。逻辑上分两步遍历s统计每个字符的频率存进哈希表。遍历t每遇到一个字符就把哈希表里对应的计数减 1。如果某个字符在哈希表里不存在减完之后变成负数说明t里出现了s没有的字符直接返回 false。遍历完t之后如果哈希表里所有计数都恰好归零说明两个字符串的字母种类和数量完全匹配。这个思路的复杂度是 O(n)看起来已经比排序法优秀了。但注意这里用的是通用哈希表。在只包含小写字母的限制下哈希表未必是最好的选择——下面这一节就专门聊这个。2. 核心解法细节拆解哈希表与数组的选择逻辑2.1 为什么数组在本题能替代哈希表很多人的第一反应是“用哈希表啊Python 里就是Counter(s) Counter(t)”写起来确实爽from collections import Counter def isAnagram(s: str, t: str) - bool: return Counter(s) Counter(t)但如果你去跑性能对比或者在实际面试里用这版总感觉少点灵魂。原因在于这道题给了一个非常强的约束——只有 26 个小写字母这意味着我们根本不需要哈希表那么“重”的数据结构一个长度为 26 的数组就够了。为什么数组能代替哈希表因为哈希表的本质是“键到值的映射”而这里的键是 26 个有规律的小写字母。我们可以把a映射到数组下标 0b映射到 1……z映射到 25映射公式极其简单index ord(c) - ord(a)ord()返回字符的 ASCII 码a是 97b是 98所以减去ord(a)之后正好得到 0 到 25 的连续整数。这样就有了从字符到下标的完美映射而且没有哈希冲突、不需要扩容、不需要处理红黑树退化问题。这背后的原理也值得展开说说。哈希表在内存中并不像数组这样“直接通过偏移量访问”而是要经过计算哈希值、定位桶、处理冲突链表或红黑树等一系列步骤。对于只有 26 个候选键的固定场景数组的随机访问是 O(1) 且常数极小的操作编译器可以直接帮你把arr[c - a]变成一条内存地址计算指令。而HashMap每次操作都有额外的方法调用和哈希计算开销常数完全不在一个量级。另外还要注意一个隐藏性能问题Java 等语言的HashMapCharacter, Integer每次往里塞值都涉及自动装箱把char包装成Character把int包装成Integer意味着会创建一堆无用的中间对象。如果字符串很长这部分 GC 压力是实实在在的。数组版本用的是基本类型数组完全没有这个烦恼。这也是为什么在算法竞赛和面试题解里只要字符集合是有限的、可枚举的大家几乎默认用数组而不是哈希表。2.2 代码实现与关键边界处理最终推荐的解法是先判断长度再用长度为 26 的数组做一加一减的核销。代码如下def isAnagram(s: str, t: str) - bool: if len(s) ! len(t): return False counts [0] * 26 for ch in s: counts[ord(ch) - ord(a)] 1 for ch in t: counts[ord(ch) - ord(a)] - 1 for count in counts: if count ! 0: return False return True这里有几个细节值得反复强调。第一个细节长度判断不能省。如果两个字符串长度都不一样那无论字母种类多么“看起来像”也绝不可能是异位词。这个提前判断能直接从根上排除大量输入避免后续无意义的遍历属于零成本的剪枝优化。第二个细节一加一减的策略。常见写法有两种。第一种是先统计s的频次再遍历t减掉第二种更聪明在同一个循环里处理两个字符串s的字符加一t的字符减一最后检查数组是否全零。第二种写法代码更紧凑但逻辑上要注意在遍历到t的某个字符时它下标处的计数可能暂时为负这是正常的因为t里当前字符的数量暂时超过了s里的数量。最终是否合法只取决于循环结束后数组是否全部归零。如果要从 Java 角度写也很直白class Solution { public boolean isAnagram(String s, String t) { if (s.length() ! t.length()) return false; int[] counts new int[26]; for (int i 0; i s.length(); i) { counts[s.charAt(i) - a]; } for (int i 0; i t.length(); i) { counts[t.charAt(i) - a]--; } for (int count : counts) { if (count ! 0) return false; } return true; } }注意 Java 里s.charAt(i) - a是利用了char参与算术运算时会自动转成int的特性本质上和 Python 里的ord(ch) - ord(a)是同一个东西只是语法上更隐晦。2.3 时空复杂度的完整推导我们来把这个数组解法的复杂度推导清楚因为面试官大概率会追问“你确定这是 O(1) 空间吗”设两个字符串长度分别为 n题目保证了不一致时已经直接返回 false所以后续都默认长度相同。时间复杂度两个循环分别遍历s和t各需要 O(n) 次操作最后检查长度为 26 的计数数组需要 O(26) 次操作。总的复杂度是 O(n 26)在 n 远大于 26 的场景下取主导项 O(n)。你可以把它理解为 O(n)因为那个常数 26 在 n 面前可以忽略。空间复杂度我们只申请了一个长度为 26 的整型数组大小是固定的和输入字符串的长度无关。所以空间复杂度是O(1)。注意这里的 O(1) 指的是“不随 n 增长”不是说用了 0 个额外空间。对比一下三种解法的复杂度解法时间复杂度空间复杂度适用性排序法O(n log n)O(n)取决于语言的具体排序实现思路最简单适合暴力验证哈希表计数O(n)O(k)k 为字符种类数量通用性最强适合任意字符集定长数组计数O(n)O(1)数组长度固定为 26仅适合字符集可枚举且范围固定的场景从刷题和面试的角度定长数组方案是这道题性价比最高的答案。但有些读者可能会想“不对我听说空间复杂度还有一种说法是 O(1)是因为整理字符集固定为 26 个字母所以可以视为常数空间。” 这个理解完全正确而且这正是 O(1) 空间说的依据。字符集的大小和输入规模无关它是一个常数所以空间是常数级的。3. 时空优化全攻略从暴力到最优的演进路线3.1 从 O(n log n) 到 O(n)排序解法不是最优选项排序法胜在直观但在实际生产中如果数据量一旦上来O(n log n) 和 O(n) 的差距会非常明显。举个例子假设字符串长度是 1 万排序法的操作量大约是10000 * log2(10000) ≈ 130000次比较而数组计数法只需要大约2 * 10000 20000次数组操作。当长度变成 100 万时差距会进一步扩大到几十倍甚至上百倍这还不算排序过程中的元素交换和额外内存分配。所以我在刷题时给自己定了个规矩凡是遇到“判断两组数据是否构成某种映射关系”的题先想想能不能用计数或哈希解决排序只作为保底方案。LeetCode 242 就是这个思路的完美启蒙题理解透以后后面很多“字母频次”相关的题目比如 LeetCode 49 字母异位词分组、LeetCode 383 赎金信都能顺下来。趁这个机会多说一句LeetCode 242 几乎是 LeetCode 49 的前置技能点242 学不会49 的分组解法也会很吃力因为分组的核心同样是“把异位词映射到同一个特征值”。3.2 空间 O(1) 的进一步优化提前剪枝与计数器优化数组计数法本身已经是 O(1) 空间了但实际代码里还能抠出几个优化点提前判断长度不相等。这个前面说了是剪枝绝不是可有可无的装饰。遍历过程中可以提前退出吗注意一个细节如果用“先加后减”的写法在遍历t的某个字符时如果发现计数已经减到负数实际上可以立刻返回 false因为这说明t里这个字符的出现次数已经超过了s后续无论怎么核销都不可能归零了。不过这个优化只在两个字符串长度相同的前提下才正确否则可能漏掉长度差异的检查。代码可以改成def isAnagram(s: str, t: str) - bool: if len(s) ! len(t): return False counts [0] * 26 for ch in s: counts[ord(ch) - ord(a)] 1 for ch in t: idx ord(ch) - ord(a) counts[idx] - 1 if counts[idx] 0: return False return True这个版本的优点是大多数情况下可以提前结束不需要等完全遍历完t再检查全数组。最坏情况合法异位词时依然要全部遍历复杂度不变但平均性能更优。“先统计后核销”和“同循环一加一减”选哪个我个人的建议是面试时优先写“先加后减再检查”的版本因为它逻辑最好讲、最不容易出错“同循环一加一减”虽然代码短但需要额外解释负数状态的含义容易绕晕别人。效率上来讲两者差距微乎其微面试的核心是让对方快速理解你在做什么。3.3 进阶场景Unicode 字符与更通用的解法刚才我们一直说“题目限制小写字母”那如果面试官加一句“如果输入包含 Unicode 字符比如中文、emoji你的解法还适用吗” 这就到了考察你是否真懂原理的时候了。答案分两层数组方案不行了。因为 Unicode 的字符范围太大超过 100 万个码点为每一个码点都分配一个数组下标要么数组长度不可接受要么绝大多数位置都是空置的内存浪费。通用哈希表方案依然适用。我们不需要预知字符的枚举范围只需要把每个字符作为键存进哈希表就行遇到什么存什么。长这样def isAnagram(s: str, t: str) - bool: if len(s) ! len(t): return False from collections import defaultdict counts defaultdict(int) for ch in s: counts[ch] 1 for ch in t: counts[ch] - 1 return all(count 0 for count in counts.values())在 Java 中还要注意一个细节如果用HashMapCharacter, Integer对于char类型只能覆盖 UTF-16 编码单元范围内的字符如果遇到超出基本多语言平面的 Unicode 字符比如某些生僻汉字、emoji 序列字符会被表示成两个char代理对直接HashMapCharacter, Integer会统计错。正确的做法是用码点code point作为键例如用s.codePoints()流式处理或者干脆把字符串换成数组再迭代码点。这个话题比较深面试里不一定会追问这么细但如果对方问了你能答到这个层面绝对是一个很大的加分项。从题目本身来说还有个很自然的延伸LeetCode 49 字母异位词分组。解法就是把每个词排序后的结果或计数特征作为哈希表的键把同组的异位词归到一起。所有这类题本质上都在做一件事——为“异位词等价类”找一个稳定、可比较的特征值。有的特征值是排序后的字符串有的是 26 个计数的组合表示。理解了这一层LeetCode 242 就不仅仅是“一道简单题”而是一整套“频次统计类题目”的思想基石。4. 常见问题与排查技巧实录4.1 面试中容易被追问的三个问题第一个问题“你为什么不直接用排序”这时候你要答出“排序是 O(n log n)”并且把常数优化也提一嘴展示你对比过不同方案的复杂度。面试官想听的不是标准答案而是你有没有真正分析过。第二个问题“你的空间究竟是多少怎么可能是 O(1)”很多候选人会脱口而出 O(1)但一问“为什么是 O(1) 而不是 O(n)”就支支吾吾。正确回答是我们申请了一个固定长度为 26 的数组它的长度不会随着输入字符串长度 n 的变化而变化因此空间开销是常数级别。如果字符集变成所有 ASCII 字符长度可能是 128 或 256但仍然是常数。只有字符集范围不可预知比如一般性的 Unicode我们才需要 O(k) 的空间此时如果 k 可能很大就不能叫 O(1) 了。第三个问题“你能再优化吗”说实话在“只有小写字母”的约束下数组计数法已经到最优了很难再往时间复杂度上压。但你可以说如果允许对输入做预处理可以在更早的阶段用长度判断提前返回如果追求代码并发性能可以把统计和核销拆成两个循环甚至用并行流处理如果想继续减少空间可以用位运算但 26 种字母的数量可能超过 1 位位运算意义不大。答到这面试官基本知道你真的理解了各种方案的天花板在哪里。4.2 刷题过程中常见的低级错误这题看着简单但我在给代码 review 时还是见过不少坑这里列几个最典型的错误一忘记判断长度。没有len(s) ! len(t)的提前判断代码也能跑但后面一加一减时数组状态会混乱。尤其是使用提前退出优化时不判断长度会直接导致错误结果。比如s abt a遍历完t后 counts 数组可能是{a: 1, b: 1}此时有的计数值为正有的为负最后检查全零时照样能拦截住。但如果你用了提前退出减到负数就返回在t a遍历到字符a时计数从 1 减到 0不会触发退出最终返回时数组不全为零才能正确判断为 false。乍一看不判断长度好像也能过但本质上这个方案依赖最后全零检查而且会多做无效遍历。所以无论怎样长度判断都是最简单稳妥的第一刀。错误二数组下标越界。如果输入里混入大写字母比如s Ab、t bA那么A - a的结果是65 - 97 -32数组下标直接变成负数轻则结果错误重则导致运行时异常。所以面试时最好先和面试官确认输入范围如果题目没明说只含小写字母要么先统一转小写要么直接改用哈希表方案。错误三用 Python 的Counter直接比较时忽略长度判断。Counter(s) Counter(t)本身已经能判断字母频次是否一致它天然包含长度信息所以长度判断可加可不加。但如果你先比较len(s) ! len(t)可以避免创建两个Counter对象的开销。当字符串很长时这部分内存和 CPU 开销还是可感知的。错误四在遍历t时修改哈希表并删除键。有的同学喜欢在遍历t时如果计数值减到 0 就从哈希表里删除该键最后检查哈希表是否为空。这个思路是对的但要注意在 Java 的HashMap里不能在 for-each 遍历的同时直接删除键否则会抛ConcurrentModificationException需要用迭代器的remove()方法。这种细节在 LeetCode 上不会报错因为单线程但在真实工程里非常容易踩雷。4.3 一道题背后的刷题方法论延伸最后想说点方法论层面的东西。很多人刷题喜欢按“简单题 / 中等题 / 困难题”分类但我的习惯是按数据结构特征分类。LeetCode 242 这类题属于“频次统计 哈希映射”的入门题做完它之后应该主动做两件事。第一横向对比同类型题目。比如 LeetCode 383赎金信、LeetCode 49字母异位词分组、LeetCode 438找到字符串中所有字母异位词这几道题和 242 的思路一脉相承核心都是“用计数数组或哈希表统计字符频次”。把这一组题目放到一起集中刷会比零散刷题高效得多。第二思考数据结构选择的底层逻辑。为什么 LeetCode 242 用数组因为字符种类少而固定。为什么 LeetCode 49 可以用排序后的字符串当键因为排序后的结果对异位词是稳定的。如果你能在“用什么数据结构”之前先问一句“这个数据的取值范围是什么、是否需要支持动态增长”你会发现很多题目的答案不是靠死记硬背而是推导出来的。还有个有意思的事情LeetCode 242 在“热门 100 题”里的地位很微妙它本身只是简单题但你会发现在讨论各种进阶题目时很多人都会拿“字母异位词”当例子来讲哈希表和排序。比如 LeetCode 周赛里出现过的字符串题目不少都能看到 242 的影子。所以别因为它简单就跳过把简单题的多种解法、复杂度边界、字符集变化的影响都吃透后面遇到复杂字符串题的时候你会感谢现在认真抠细节的自己。这题我刷过无数遍面试时也用它考过不少人。说实话能写出最优解的人很多但能把“为什么不用更通用的哈希表”“空间复杂度为什么是 O(1)”“换成 Unicode 怎么办”这三个问题都答利索的人确实不多。如果你正在准备面试建议把这三个追问自己先在纸上写一遍答案练到不用思考就能脱口而出为止——这种基本功才是 LeetCode 刷题真正的复利所在。