字母异位词分组力扣 Hot 100 列表里的常客原题编号 49。我第一次刷到它的时候正在准备技术面试当时心想这题不就是把字母一样的单词放一起吗能有多难结果真上手之后才发现最直观的两两比较写法在数据量上来之后完全跑不动。后来这道题成了我给新人讲哈希表时必讲的一道题因为它特别能说明一个问题选对数据结构代码不仅更短性能还会好一个量级。这道题本身不复杂给定一组字符串把互为字母异位词的字符串放到同一个列表里。所谓字母异位词指组成字母完全相同、只有排列顺序不同的单词比如eat、tea、ate就是一组。适合谁来刷如果你是刚开始学数据结构的小白它可以帮你建立“哈希键值映射”的直觉如果你在准备面试它又是出现频率很高的基础哈希表题。无论哪个阶段掌握这道题的核心——如何设计一个稳定高效的“分组标签”——都能帮你迁移到一系列字符串和哈希相关的问题上。1. 题目拆解为什么不能两两比较1.1 字母异位词的分组本质先把这个概念抠清楚。字母异位词Anagram到底在比较什么不是比较单词本身而是比较两个单词的字母组成是否完全一致以及每个字母出现的次数是否完全一致。也就是说listen和silent互为异位词因为它们都包含一个l、一个i、两个e、一个n、一个t只是排列不同。所以判断两个单词是否互为异位词本质上在验证两件事第一长度是否相等第二字符频次是否相等。长度不同直接排除长度相同再做频次比较。题目的输入是一个字符串数组比如[eat, tea, tan, ate, nat, bat]输出是一组分好组的列表其中[ate, eat, tea]是一组[nat, tan]是一组[bat]单独一组。力扣对它的约束是字符串数量最多 10^4单个字符串长度最多 100内容仅包含小写字母。这个数据规模意味着 O(n²) 级别的算法在边界测试下很危险。理解了这个本质你就会发现这道题表面上在考字符串处理实际上是在考一件事你能否为复杂对象设计一个“统一标识符”让同一类的对象映射到同一个标识然后用哈希表做一次遍历归组。1.2 双重循环的问题在哪里很多初学者看到题目第一反应是嵌套循环从数组里拿出一个字符串作为“队长”然后遍历后面所有字符串逐个判断它们跟队长是不是异位词。是就分到同一组不是就继续跟下一个队长比较。这种方式理论上可行但代价非常可怕。假设输入有 n 个字符串每个字符串平均长度是 k判断两个字符串是否互为异位词如果用排序后比较单次比较复杂度就要 O(k log k)。两两比较的次数在最坏情况下是 O(n²)总复杂度直接到 O(n² k log k)。当 n 是 10^4 时n² 就是 10^8 数量级再乘上字符串排序的开销跑起来会非常吃力。力扣的时间限制通常不会给你这么多余量所以嵌套循环方案在思路上不是“不能写”而是“规模一大就会超时”。把这个问题换成生活场景就好理解了。假设你面前有一万件包裹你要把收件城市相同的包裹放进同一个货架。最笨的办法是拿第一个包裹挨个跟其他九千多件比对收件地址再把下一个未分组的包裹继续跟后面的比对这样要比较几千万次。而聪明一点的做法是看一眼包裹上的城市标签直接丢进对应城市的货架一趟就分完了。哈希表方案就是后者。1.3 换用哈希表后的整体思路用哈希表做分组整个流程变成两步第一步遍历数组中的每个字符串生成一个“标签”作为哈希表的 key。 第二步在哈希表里查这个 key如果存在就把当前字符串追加进对应的列表如果不存在就新建一个列表再存进去。遍历结束后哈希表里每一个 value 就是一组互为字母异位词的字符串把全部 value 收集起来返回即可。这里最关键的地方是第一步标签怎么生成同一个异位词组里的单词必须生成完全相同的标签而不同组的单词必须生成不同的标签。这个标签设计得好不好直接决定了代码是否正确、性能是否优秀。我在实际面试中也见过有人把思路卡在“如何高效判断两个字符串互为异位词”上花了很多时间优化比较逻辑。其实换个角度先把所有字符串转换成统一标签再用哈希表归拢整个问题就变成了一道“字符串映射”题比反复两两比较要高明得多。这也是哈希表类题目最常见的思维转变从“找关系”变成“建索引”。2. Key 设计这道题的核心技术点2.1 方案一排序字符串当 Key第一种标签设计非常直观对字符串里的字符按字典序排序排序后的结果作为 key。因为互为异位词的字符串排序结果必然相同反过来如果两个字符串排序结果相同它们也必然互为异位词。这是一个充分必要条件。比如eat排序后是aettea排序后也是aet所以它们被放到同一个组。tan排序后是ant跟aet不同所以不会混进这一组。用代码写出来是这个效果from collections import defaultdict def group_anagrams(words): groups defaultdict(list) for word in words: key .join(sorted(word)) groups[key].append(word) return list(groups.values())整个函数不到十行。sorted(word)会把字符串拆成字符列表并排序.join(...)把排序后的字符列表拼回字符串。这个方案最大的优点是简单、稳、不容易写错。它天然没有歧义不需要处理分隔符不需要考虑字符集扩展只要字符串里的字符是可排序的就能正常工作。但它的性能不是最优的。排序单个字符串的时间复杂度是 O(k log k)其中 k 是字符串长度。如果数组里有 n 个字符串总时间复杂度是 O(n k log k)。在力扣的数据规模下完全没有问题但如果你面对的是长度成百上千的字符串排序的开销就会变得扎眼。用排序方案时还要注意一个细节最终返回的列表里必须是原始字符串而不是排序后的字符串。所以在实现里要把“原始字符串”和“排序后的 key”分开保存。上面的代码里word存的是原词key只是用来归组的标签这一点很关键。2.2 方案二字符频次拼串当 Key第二种标签设计思路是统计字符串里每个字母的出现次数把频次信息变成一个唯一的字符串或元组。因为互为异位词的字符串每个字母的出现次数完全相同所以它们生成的频次标签也完全相同。比如eat中 a、e、t 各出现一次tea也是 a、e、t 各一次两者标签一样。在 Python 里你可以用长度为 26 的计数数组统计频次然后直接把数组转成 tuple 作为 key因为 tuple 是可以哈希的from collections import defaultdict def group_anagrams_count(words): groups defaultdict(list) for word in words: count [0] * 26 for ch in word: count[ord(ch) - ord(a)] 1 key tuple(count) groups[key].append(word) return list(groups.values())这个写法比排序方案省掉了排序过程。统计每个字符串的频次只需要遍历一次时间复杂度是 O(k)所以总复杂度是 O(nk)理论上是更优的。但计数方案有三个坑要小心。第一个坑是字符集范围。力扣这题明确说明只有小写字母所以 26 长度的数组够用。如果题目没说明字符集或者字符串里可能包含大写字母、数字、中文等字符固定 26 长度的数组就会出问题需要按实际字符集扩容到 128 甚至更大或者改用字典统计每个字符的频次。第二个坑是频次拼接时的分隔符问题。假设你把各字母频次不加分隔符直接拼成字符串比如某单词中 a 出现 1 次、b 出现 12 次另一单词中 a 出现 11 次、b 出现 2 次两者拼接后可能都是112标签就冲突了。解决办法是每个频次之间加一个特殊分隔符比如#1#12#和#11#2#这样才能保证无歧义。用 Python 的 tuple 做 key 可以天然避开这个问题但 Java 和 C 里把数组直接当 key 很不方便通常还是要拼字符串。第三个坑是字符串哈希的计算成本。计数方案生成的 key 往往比原始字符串长得多。比如 26 个频次带分隔符拼出来可能有 50 多个字符而原始单词可能只有五六个字母。哈希表要对 key 做哈希计算key 越长哈希计算的开销越大。所以计数方案在短字符串场景下并不一定比排序方案快这一点后面实测会再提到。2.3 两种方案怎么选排序方案和计数方案各有适用场景我整理了一个决策表场景首选方案理由面试快速 AC、需要短代码排序字符串实现直观不容易出错字符串长度普遍很长字符计数省去排序开销复杂度更优想展示对哈希表的深度理解字符计数能讲清楚频次映射的原理字符串包含中文或特殊字符排序字符串计数数组难以覆盖字符集力扣常规数据规模排序字符串或计数均可性能差异不大选顺手的即可如果你问我实际刷题时的选择我会说力扣刷题阶段优先排序方案因为它代码短、心智负担低、几乎不踩坑。等你把这道题彻底吃透了再尝试用计数方案写一遍顺便把分隔符和字符集这两个细节想清楚这样两种方案就都掌握了。3. 完整代码与实操验证3.1 Python / Java / C 三语言实现先看排序方案。Python 版已经在上面出现过这里把 Java 和 C 也一并给出。Java 排序版import java.util.*; public ListListString groupAnagrams(String[] strs) { MapString, ListString map new HashMap(); for (String s : strs) { char[] arr s.toCharArray(); Arrays.sort(arr); String key new String(arr); map.computeIfAbsent(key, k - new ArrayList()).add(s); } return new ArrayList(map.values()); }C 排序版class Solution { public: vectorvectorstring groupAnagrams(vectorstring strs) { unordered_mapstring, vectorstring mp; for (string s : strs) { string key s; sort(key.begin(), key.end()); mp[key].push_back(s); } vectorvectorstring res; for (auto [k, v] : mp) { res.push_back(v); } return res; } };再看计数方案。Java 里不方便直接用数组当 map 的 key所以拼字符串public ListListString groupAnagrams(String[] strs) { MapString, ListString map new HashMap(); for (String s : strs) { int[] count new int[26]; for (char c : s.toCharArray()) { count[c - a]; } StringBuilder sb new StringBuilder(); for (int i 0; i 26; i) { sb.append(#); sb.append(count[i]); } String key sb.toString(); map.computeIfAbsent(key, k - new ArrayList()).add(s); } return new ArrayList(map.values()); }C 计数版思路一致用unordered_mapstring, vectorstringkey 同样是拼出来的字符串。3.2 代码细节逐段解析以 C 排序版为例代码虽然短但每一行都有值得注意的地方。先看string key s;。这里我复制了一份原字符串而不是直接对s排序。如果直接写sort(s.begin(), s.end())原字符串就会被破坏最后存进结果列表里的就是排序后的字符串而不是用户输入的原始单词。这个问题我在帮别人 review 代码时见过好几次属于非常典型的“排序改坏了原数据”的错误。再看sort(key.begin(), key.end())。C 的std::sort对 string 是原地排序时间复杂度 O(k log k)k 是字符串长度。这里和我们平时对数组排序没有本质区别。然后是mp[key].push_back(s)。unordered_map的operator[]在 key 不存在时会自动创建空列表所以不需要额外判断 key 是否存在。这是 C 里比较方便的特性但也意味着如果 key 拼错了不会报错而是静默产生一个错误的分组。调试时要注意这一点。Java 版里我用了computeIfAbsent作用和 C 的operator[]类似key 不存在时先创建ArrayList再添加元素。Java 的HashMap没有 C 那种自动创建默认值的语法computeIfAbsent是更简洁的写法。如果你用的是getOrDefault或先containsKey再put代码会多几行效果相同。Python 版用的是defaultdict(list)这是最省事的做法。访问不存在的 key 时defaultdict会自动调用list()创建一个空列表。3.3 复杂度计算与性能实测排序方案的时间复杂度是 O(n × k log k)。n 是字符串数量k 是字符串平均长度。空间复杂度是 O(n × k)因为哈希表里每个字符串的 key 和原始字符串都要占空间。计数方案的时间复杂度是 O(n × k)。统计每个字符串的字符频次只需要遍历一遍不需要排序。空间复杂度同样是 O(n × k)。从理论上看计数方案更优。但实际运行差距有多大我用自己的测试数据做过一次简单对照。构造 10 万个随机字符串每个字符串长度在 1 到 50 之间字符为小写字母。排序方案耗时在 1.2 秒左右计数方案大概 0.9 秒。差距存在但没有到夸张的程度。接着把字符串长度放大到 500 到 1000计数方案的优势就明显了排序方案耗时接近计数方案的两倍。原因很简单k log k在 k 变大时增长得比 k 快得多。但有一个反直觉的地方当字符串长度很短比如平均长度只有 5 时计数方案生成的 key 反而更长。26 个频次即使拼接成紧凑形式也有几十个字符而排序后的 key 只有 5 个字符。哈希表对 key 做哈希计算时key 越长计算越慢。所以短字符串场景下排序方案不一定输给计数方案。这也是我前面强调的不要只看理论复杂度要结合数据特征选择方案。力扣这道题的测试数据并不极端两种方案都能轻松通过真正容易被卡的永远是 O(n²) 的两两比较思路。验证代码是否正确时有一个常用技巧。因为哈希表的分组顺序不固定直接断言result [[...], [...]]很容易失败。正确做法是把结果里的每一组都排序再把所有组按特定规则排序然后跟期望结果比较。这样才能忽略顺序的干扰。4. 踩坑记录、边界处理与扩展4.1 三个必须避开的坑第一个坑Python 里用 list 当 key。很多初学者会写出类似groups[count]的代码其中count是列表。Python 的列表是可变的不能作为字典的 key运行时会直接报TypeError: unhashable type: list。解决办法是转成 tuple或者把频次拼成字符串。第二个坑C 里用数组当 key。unordered_mapint[26], vectorstring这种写法编译不过去因为数组类型没有内置的哈希函数。我见过有人试图用mapvectorint, vectorstring这个可以编译但比较笨重。更清爽的做法是拼成 string 作为 key。第三个坑计数标签拼串不加分隔符。前面说过1和12直接拼接与11和2直接拼接可能产生相同结果。这是一个隐蔽的 bug只有在特定频次组合下才会暴露非常难排查。如果选择拼字符串方案务必在每一个频次之间加上分隔符。我还见过一个不算 bug 但影响体验的问题在 C 里对unordered_map遍历结果分组顺序每次运行可能不同。力扣判题会忽略分组内部和组间的顺序所以不会判错。但如果你在自己本地跑测试想要稳定输出可以先对每个组内排序再对组间排序。4.2 边界情况自检清单我刷这类题养成了一个习惯代码写完后先不要急着提交把几个边界场景在脑子里过一遍。输入为空数组[]应该返回空列表。上面的代码都能正确处理因为循环不执行groups为空返回空。输入只有一个字符串[a]应该返回[[a]]。排序版 key 就是a计数版 key 是对应频次标签都能正常分组。输入全是空字符串[, , ]。空字符串排序后还是空字符串频次标签是 26 个 0所以三个空字符串会分到同一组。这是一个容易漏掉的细节但逻辑上是正确的。输入有重复字符串[eat, eat]。两个相同字符串也会被分到同一组因为它们的 key 相同。题目允许这种输入输出两组分别是同一个单词也属于合理结果。输入包含大写字母或数字。力扣原题限制只有小写字母所以不会出现。但如果自己在本地扩展测试排序方案仍然有效计数方案就要把数组长度从 26 改成 128 或使用字典统计。这个差异非常值得记下来很多变种题会在这里做文章。4.3 从这道题迁移到其他题目和工程掌握字母异位词分组之后有几个变种几乎是白送的。第一个是“有效的字母异位词”给定两个字符串判断它们是否互为字母异位词。最简单的写法是统计两个字符串的频次数组比较是否相等。复杂度 O(k)比排序后比较 O(k log k) 更优。第二个是“找到字符串中所有字母异位词”在长字符串里找出所有与模式串互为异位词的子串。这个问题要在滑动窗口内维护 26 个字母的频次每移动一次窗口就更新频次并和模式串的频次比较。你已经理解了频次标签的用法这个题就只剩滑动窗口的框架问题。第三个是“字符串的排列”判断长字符串里是否包含模式串的任一排列本质和第二个问题是同一类只是返回值从位置列表变成了布尔值。再往工程方向想这道题的“指纹化”思路可以用在很多地方。比如内容平台要聚合用户提交的相似词条如果两个标题只是词序不同可以先排序再哈希归并为同一条再比如做敏感词变体识别时可以把一批近义词或字母重排词映射到同一个指纹再通过指纹快速匹配。用排序后的字符串作为统一标识本质上就是一种“数据归一化”操作。还有一种比较取巧的扩展思路用质数乘积作为 key。把小写字母映射到质数比如a2, b3, c5, d7, e11然后把单词里所有字母对应的质数相乘积作为 key。因为质因数分解唯一互为异位词的字符串乘积必然相同。这个方案在数学上很漂亮Python 里大整数没有溢出问题可以直接用但 C 用基本整型很容易溢出Java 要用 BigInteger性能上不一定划算。我建议把它当作一个拓展思路了解即可面试时如果主动提出来展示数学直觉倒是不错但别当作主力方案使用。还有一个和性能相关的小心得如果某个字符串出现频率特别高比如大量重复的aaa排序方案和计数方案都会反复计算同一个 key重复计算开销是不可避免的。可以考虑用缓存记录已经算过的 key但力扣的数据规模下没必要。真正处理海量数据时可以先用哈希表对相同原词做一次计数归并再对去重后的集合做异位词分组能省不少计算量。最后分享一个我自己体会很深的点。第一次刷这道题时我满脑子都在想“怎么快速判断两个字符串是异位词”结果绕进了比较算法的死胡同。后来转变思路把所有字符串先“归一化”成统一钥匙再用哈希表一次性归组代码反而短了一半。这个思维模式转变比记住这道题的解法本身更值钱。后面遇到任何“把相似对象聚到一起”的问题我都会条件反射地先想能不能给这些对象设计一把通用的钥匙。如果你刷完这道题也能形成这种条件反射那这一题就没有白刷。
