很多刷题的人看到“力扣No.242有效的字母异位词”这道题第一反应是“这不就是个入门题嘛直接跳过”。我之前也这么想过直到有一次在线下技术交流里聊到这道题发现大部分人都能写出解法但能把原理、复杂度边界、隐藏考点讲清楚的少之又少。这道题表面是“判断两个字符串的字符构成是否相同”但背后牵连着哈希表的本质、字符集与空间复杂度的关系、排序与计数的取舍甚至还有面试官最爱追问的Unicode进阶场景。这篇文章就用从业者的视角把这道题彻底拆开——从最朴素的解法到进阶变体从原理到工程经验全部过一遍。1. 为什么“有效的字母异位词”这道题值得从头到尾聊一遍先说清楚概念。所谓“字母异位词”Anagram指的是两个字符串中每个字符的出现次数完全相同只是排列顺序不同。典型例子是anagram和nagaram字符都是三个a、一个n、一个g、一个r、一个m只是顺序打乱了。反过来rat和car就不是因为字符构成压根不一样。1.1 它听起来简单但信息密度很高这道题的“简单”是LeetCode官方给的难度评级。但作为过来人我想说的是难度标签只能说明它不需要复杂的算法设计不代表它不值得认真对待。它几乎是后面一系列中等题、困难题的“地基”。比如LeetCode的“字母异位词分组”题核心思路就是把每个字符串排序后用排序结果做分组键或者用计数数组生成唯一签名再比如“字符串的排列”题判断一个字符串是否包含另一个字符串的排列本质就是滑动窗口加计数比较。这些题的思想源头都可以追溯到这道No.242。换句话说如果你能把这道题的几种解法、复杂度、边界条件聊透后面的很多字符串题会顺畅很多。1.2 面试中的“送分题”往往最能暴露水平面试场景里这类题经常作为电话轮或一面的开场题。它的目的不是考验你能否解出来而是考察你的沟通习惯、思考路径和代码风格。同样写一个HashMap计数版本有人会先问清楚字符集范围再决定用数组还是哈希表有人会先判断两个字符串长度是否相等避免后面的无意义计算有人会在循环里只用一个for循环同时完成“加计数”和“减计数”最后统一检查是否全零。这些差别面试官一眼就能看出来。所以这道题虽然简单但它其实是一道很标准的“筛子”题——筛掉那些只会背题解、不理解原理的人。2. 解法一用哈希表计数先理解“数什么”和“怎么比”2.1 核心思路把“是否异位词”转化为“字母频次是否相等”判断两个字符串是否为字母异位词本质上是在判断两件事第一字符集合是否一致第二每个字符出现的次数是否一致。只要这两点满足顺序不同完全无所谓的。那怎么统计“每个字符出现的次数”最直接的办法就是用哈希表。键是字符值是该字符在字符串中出现的次数。第一个字符串用来记录第二个字符串用来核对。具体步骤是如果两个字符串长度不同直接返回false。这是一个很小的剪枝但很关键。遍历第一个字符串中的每个字符在哈希表中将对应计数加一。遍历第二个字符串中的每个字符在哈希表中将对应计数减一。遍历结束后检查哈希表中是否存在非零的计数。如果某个字符的计数不为零说明两个字符串的字符频次不一致返回false全部为零则返回true。这里有一个值得注意的细节我上面说的是“先全部加再全部减最后检查”但工程上还有一个更好的写法——在遍历第二个字符串时同步检查。public boolean isAnagram(String s, String t) { if (s.length() ! t.length()) { return false; } MapCharacter, Integer map new HashMap(); for (char c : s.toCharArray()) { map.put(c, map.getOrDefault(c, 0) 1); } for (char c : t.toCharArray()) { Integer count map.get(c); if (count null) { return false; } map.put(c, count - 1); } for (int count : map.values()) { if (count ! 0) { return false; } } return true; }这种“加一减一”的写法看起来只是简单的计数操作但它背后有一个很通用的思维模型用正负抵消来比较两个序列的统计特征。以后做“找出唯一不同的字符”“判断能否通过重新排列得到另一个字符串”这类题时这个模型都能复用。2.2 为什么要在遍历第二个字符串时“边减边查”不知道你有没有遇到过这种情况第二个字符串里出现了第一个字符串完全没有出现过的字符但你没在遍历时检查null最后靠遍历哈希表的那一步也能发现计数不为零。所以“边减边查”其实不是必须的但它是一个更早失败、更快返回的优化。比如s abct abx在减到x的时候就已经可以确定不是异位词了没必要把整个t遍历完再检查。对于超长字符串这种提前终止能省一轮遍历的时间。当然前提是你得记得处理map.get(c)返回null的情况不然会直接抛出空指针异常。2.3 哈希表方案的适用边界字符集不确定时的首选用HashMap最大的好处是通用。它不关心字符集是什么不管你是ASCII字符、中文汉字、emoji还是任意Unicode字符都能正确处理。面试中如果被追问“如果输入从26个英文小写字母扩展到所有Unicode字符怎么办”哈希表方案几乎不需要修改就能继续工作。这点在后面的“进阶场景”里还会细说。3. 解法二用数组模拟哈希表面试里最推荐的写法3.1 为什么可以用数组代替哈希表题目里有个很关键的前提条件——多数版本里只说“字符串只包含小写字母”。这句话意味着字符集是确定的只有26个英文小写字母。既然字符集大小已知且范围紧凑我们就可以直接用数组来代替哈希表。a到z的ASCII码是连续递增的用当前字符减去a就能得到一个0~25的索引值映射到数组的26个位置上。数组的索引天然就是哈希表的键索引对应的值就是计数。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]; counts[t.charAt(i) - a]--; } for (int count : counts) { if (count ! 0) { return false; } } return true; }注意到没有这里只用了一个数组。遍历过程中对s的字符做加法对t的字符做减法最后数组里所有位置都归零就说明两个字符串的每个字符频次完全一致。这个写法比维护两个数组再逐个比较更简洁。3.2 数组方案为什么比HashMap快很多初学者会奇怪数组方案和哈希表方案在时间复杂度上都是O(n)为什么实际运行差距那么大核心原因有三个第一HashMap的键是Character对象。char是基本类型放进Map时会经历装箱boxing操作频繁的创建和回收对象是有开销的。第二HashMap的底层是数组加链表或红黑树需要先计算哈希值、定位桶位置遇到哈希冲突还得走链表或树查找。而数组方案是直接通过索引访问相当于每次计数都是精确命中没有任何查找开销。第三扩容问题。HashMap在元素数量超过阈值时会触发扩容扩容涉及重新哈希性能抖动明显。而固定大小的int[26]从头到尾都不会有这种开销。实测下来在处理几百万个字符的测试用例时数组方案的耗时会明显低于HashMap方案差距可能在一个数量级左右。虽然刷题场景里数据量通常没那么大但这种理解能帮你建立“数据结构选型要贴合数据规模”的直觉。3.3 一个容易写错的细节char参与运算的类型counts[s.charAt(i) - a]这里的运算有个隐藏知识点char在Java里本质上是一个无符号16位整数。当char与char做减法时它们会被提升为int类型参与计算所以结果是一个int值可以直接作为数组索引。我见过有同学试图这么写counts[s.charAt(i)];这样编译都过不了或者运行时报ArrayIndexOutOfBoundsException因为字符的ASCII码比如a是97远超数组长度26。记住必须先减去a把字符映射到0~25的区间内。4. 解法三排序法最朴素但最“吃场景”的方案4.1 排序法的思路与实现除了计数还有一条完全不同的思路把两个字符串排序如果排序后内容一致就说明它们互为字母异位词。为什么排序可行因为异位词的本质是“字符多集multiset相同”而排序刚好能把顺序差异抹平留下唯一的有序序列。就像两副打乱的扑克牌整齐排好之后比的还是同花色的牌有哪些、各有几张。在Python里这个解法写起来最短def is_anagram(s: str, t: str) - bool: return sorted(s) sorted(t)在Java里稍微绕一点因为String是不可变对象不能原地排序。常见写法是转成char[]排序再转回String比较或者直接用Arrays.equals比较两个char[]public boolean isAnagram(String s, String t) { if (s.length() ! t.length()) { return false; } char[] charsS s.toCharArray(); char[] charsT t.toCharArray(); Arrays.sort(charsS); Arrays.sort(charsT); return Arrays.equals(charsS, charsT); }4.2 排序法的时间复杂度代价排序法的时间复杂度是O(n log n)受限于比较排序的下界。如果字符串长度是10万哈希表方案大约跑10万多步排序法要跑接近160万次比较按n log n估算准确说每次比较本身也带常数开销。那为什么排序法还是一个值得掌握的方案因为它有极具竞争力的使用场景。当字符集非常大或不确定时计数方案就会遇到麻烦数组长度没法预先确定或者需要开一个巨大的稀疏数组造成空间浪费这时候你只能改用HashMap。而排序法根本不在乎字符集范围你只需要一个能对所有元素排序的规则即可。所以如果你和我一样面对的是Unicode输入且不想引入额外依赖排序法反而是更省心的选择。另外排序法的代码通常最短——Python里一行搞定非常适合快速调试或用脚本验证思路。说到底对算法题要有一个基本认知没有“万金油”的解法只有“当前场景下最合适的解法”。5. 复杂度分析之外五个容易被忽略的工程细节5.1 长度判断是微优化还是必要的防御先判断长度能让长串不匹配的情况直接返回。很多人觉得这是多余的但仔细想想如果长度不等说明字符总数不同哪怕每个字符的频次再接近也不可能是异位词。这一步的代价几乎为零收益是可能省去整个遍历。所以这个判断不是可选的而是该写进习惯里的。5.2 关于空间复杂度是O(1)还是O(26)的严谨讨论力扣的官方题解里通常会写数组方案的“空间复杂度为O(1)”很多同学直接背结论却说不清为什么。严谨地说数组方案的空间开销是int[26]即占用内存大小与输入字符串的长度无关只与字符集大小相关。因为字符集是固定的26个小写字母所以可以认为空间复杂度是常数级记作O(1)。但如果题目扩展成Unicode场景字符集变成13万多个码位你依然可以开一个足够大的数组但这时候“空间与字符集大小相关”这一点就不能再说成O(1)了应该表述为O(K)其中K是字符集大小。这个细节在面试中属于加分项——能准确说清“为什么这个场景下它才是O(1)”的候选人明显比背结论的人理解更深入。5.3 输入参数为空的边界处理s 、t 两个空字符串互为异位词吗严格说抛去直觉答案是true因为空字符串本身就是由0个字符组成的字符串字符构成完全一样。代码里这个情况靠“长度相等”判断会通过进入循环后不会执行任何操作最终检查数组全零返回true。所以即使不专门写空值判断代码的行为也是正确的。但如果有洁癖也可以在开头写if (s null || t null) { return false; }LeetCode的测试用例通常不会出现null但从工程角度看防御性编程永远不会错。这个问题在线下交流时被问到过几次我就顺手提一下。5.4 各语言实现的差异对比我用Java、Python、Go分别写过这个题体验差别很大。Python版最优雅from collections import Counter def is_anagram(s: str, t: str) - bool: if len(s) ! len(t): return False return Counter(s) Counter(t)Counter本身支持比较运算直接判断两个计数字典是否相等语义清晰得像是专门为这道题设计的一样。如果不想用Counter也可以先转成list排序再比较但Counter的性能和可读性都更好。Go版的写法很接近C式的直白func isAnagram(s string, t string) bool { if len(s) ! len(t) { return false } var counts [26]int for i : range s { counts[s[i]-a] counts[t[i]-a]-- } for _, c : range counts { if c ! 0 { return false } } return true }这里有个小小的坑Go里直接用s[i]取到的是byte类型对纯ASCII字符没问题但如果字符串包含中文字符len()返回的是字节数下标索引也是按字节的直接用这个写法就会出错。刷题时题目给了“只包含小写字母”的约束所以没问题但写生产代码时一定要意识到字符串编码的差异。5.5 什么时候该用“哈希表提前减查”什么时候该用“一个数组”我现在的习惯是如果题目明确字符集是小写字母直接用数组无脑快如果题目没限制字符集用HashMap如果只是想快速验证思路、不在意常数性能用排序或Python的Counter。实际面试中最推荐的展开路径是先说思路一——用哈希表统计频次复杂度O(n)空间O(n)然后补充“由于题目限制是小写字母我们可以用固定大小的数组把空间优化到O(1)”同时给出代码。这样既展现出思考的递进性也体现出对输入的敏感度。6. 从这道题延伸出去的变体它绝不是终点如果只满足于ACAccepted这道题那确实错过了很多。我建议你做完这道题之后继续沿着它的脉络做下面几道题你会发现它们都是“同源”的6.1 变体一字母异位词分组给定一个字符串数组要求把所有互为异位词的字符串分到同一组。解法思路很清晰要么“排序后作为键”要么“计数数组转字符串后作为键”。比如把[19, 5, 0, 13]这种计数结果拼成1#0#1#...格式的签名作为键存入HashMap。这一题的难度是中等但如果你把No.242的数组计数理解透彻了核心困难也就只剩“如何设计一个不会碰撞的签名方案”了。6.2 变体二字符串的排列滑动窗口版判断字符串s2是否包含s1的某个排列。比如s1 abs2 eidbaooo答案是true因为ba就是ab的一个排列。这道题用的是滑动窗口加计数数组维护一个长度等于s1的窗口窗口内的字符计数与s1的计数一致即可判定。每次移动窗口时进来的字符加一、出去的字符减一动态比较计数是否相等。你会发现这里用的“数组计数增减比较”就是No.242的同一个内核。6.3 变体三判断两组字符串是否只差一个字符这类题经常出现在面经里给定两个字符串允许你修改其中一个字符问能否通过一次替换让它们互为异位词。做法是统计两个字符串中不同字符的个数如果恰好为2一个被删除、一个被新增同时频次差异为0就满足条件。本质上仍然是“字符频次比较”的问题。6.4 变体四进阶版Unicode字符串如果面试官追问“如果输入不只是小写字母而是任意Unicode字符比如表情符号怎么办”你要立刻意识到数组的固定长度思路失效了因为Unicode的字符空间太大。这时候可以用HashMap做完整计数也可以用CounterPython或collections.defaultdict。在Java里s.toCharArray()对基本平面内的字符还有效但遇到代理对surrogate pair表示的emoji时一个“字符”会占两个char位置你按char遍历就会把一个emoji拆成两半。正确做法是按code point遍历public boolean isAnagramUnicode(String s, String t) { if (s.codePointCount(0, s.length()) ! t.codePointCount(0, t.length())) { return false; } MapInteger, Integer map new HashMap(); int cp; for (int i 0; i s.length(); ) { cp s.codePointAt(i); map.put(cp, map.getOrDefault(cp, 0) 1); i Character.charCount(cp); } for (int i 0; i t.length(); ) { cp t.codePointAt(i); Integer count map.get(cp); if (count null) { return false; } map.put(cp, count - 1); i Character.charCount(cp); } for (int count : map.values()) { if (count ! 0) { return false; } } return true; }能当着面试官写出这个版本的人对Java字符串模型的理解是过关的。如果不熟悉codePointAt和charCount也完全可以大大方方说“生产上我会直接用第三方文本处理库来做Unicode规范化”面试官同样认可——这比你硬着头皮处理代理对更诚实、更工程化。7. 刷这道题时我踩过的坑以及现在的建议最后聊点实在的。我第一次做这道题时用的是“排序字符串再比较”的思路因为当时的想法是“字符串题就喜欢考排序排完序用equals比较稳”。AC之后就没管了。后来在某次模拟面试里面试官追问了一句“如果两个字符串很长比如一千万个字符你的方案还合适吗”我当时才意识到排序法在数据量放大之后的性能问题有多明显。也是从那次开始我养成了一个习惯每道题AC之后问自己三个问题——时间复杂度能不能再降如果能代价是什么空间复杂度有没有常数化的可能输入条件如果放宽这个解法还能不能撑住这道题的三组答案让我受益很深时间复杂度从O(n log n)降到O(n)靠计数空间从O(n)降到O(K)靠固定数组输入条件放宽靠HashMap和Unicode处理逻辑。如果你刚开始刷题我的建议是不要因为题目标着“Easy”就跳过。把这道题的三种解法都写一遍包括复杂的Unicode版。写完之后按我上面说的三个问题复盘一遍。做完这些你收获的不只是一个AC记录而是一套可以迁移到很多字符串题上的思考框架。就说这么多下一篇聊聊“字母异位词分组”那题——你会发现今天这套东西在那儿直接就能用。