LeetCode hot 100里的“字母异位词分组”这道题表面上是道入门难度的哈希表题排序加桶分组十分钟就能写完。但我在给模拟面试的候选人做讲解时发现大多数人卡住的点并不是“怎么用HashMap”而是“排序后的字符串为什么能当key”“如果不排序还能怎么分”。这两个问题想不透代码就是背模板面试官稍微变个问法就露馅。这篇文章不打算只贴一份能过题的代码而是把这道题完整拆开异位词的本质是什么、哈希签名的设计逻辑、三种主流解法的原理与坑、边界情况和面试追问的应对、以及它衍生出来的几道同族题。无论你是刚开始刷题还是准备面试想深挖细节应该都能从里面找到点东西。1. 先想清楚一个问题什么才是判断异位词的“身份证”1.1 异位词的本质是“元素多重集”和顺序无关字母异位词的定义其实很简洁两个字符串包含的字符种类相同且每种字符出现的次数也相同只是排列顺序不同比如eat、tea、ate就是一组异位词。听起来像废话但背后是一个重要的数学抽象字符串本质是“字符的多重集”顺序只是展示形式。判断两个字符串是否为异位词等价于判断它们对应的多重集是否相等。这里的关键是“多重”两个字——不仅元素集合要一样元素出现的频次也要一样。举个例子aab和aba是异位词因为字符a出现2次、b出现1次但aab和abb不是因为b的频次不同。所以判断异位词时“字母是否出现”一半“出现多少次”占另一半二者缺一不可。这个视角非常重要因为它直接引出了两种主流的“签名”方案要么把字符排序后看是否相同排序法要么统计每个字符的频次向量是否相同计数法。后面整道题的解法都围绕这两条路展开。1.2 两两比较为什么是死路很多新手第一次看到这题第一反应是双层循环逐个判断两个字符串是不是异位词是就放一起。这个思路正确而且符合直觉但复杂度是灾难级的。假设字符串数组长度为n平均每个字符串长度为k。判断两个字符串是否为异位词最坏情况需要遍历一遍并统计频次复杂度是O(k)。两两比较所有组合的复杂度就是O(n^2 * k)。一旦n到达几千操作次数就是千万级n到几万就是十亿级直接超时。更麻烦的是这种解法写起来极易出错要做去重、要管理已经分组的索引、还要维护“哪些字符串没被访问过”的标记。LeetCode上这道题的输入规模动辄上万暴力法基本不可能过。所以真正的问题变成怎样避免两两比较而是给每个字符串生成一个统一的“标识”相同异位词的标识一样不同异位词的标识不一样。这就是签名signature思想也是哈希表能派上用场的关键。1.3 签名 桶哈希分组的通用骨架把“签名”想成身份证号一群异位词虽然长相不同但他们的“异位词身份”是同一个。用这个身份做key把原字符串丢进对应的桶value里一次遍历就能完成全部分组。这套“签名 桶”的框架不仅适用于这道题几乎所有的“按某种属性归类”问题都可以套用。工程上最常见的例子是文件去重计算文件的哈希摘要签名哈希相同的文件大概率内容一样再进一步对比确认。数据库里对列做归一化比较本质也是这样先把复杂对象压缩成一个可比较的key再决定怎么分组。理解了这层逻辑剩下的就只是“签名怎么生成更高效、更不容易冲突”的取舍问题。这也是这篇文章想重点聊的东西。2. 解法一排序签名法最容易写的标准解2.1 排序为什么能当key唯一有序表示排序法的思路极其直观把一个字符串的字符按字典序重新排列得到的字符串就是它的“排好序的签名”。为什么排序结果能当唯一标识这里有一个隐含的数学事实任何一个多重集经过排序后得到的序列是唯一的。也就是说两个字符串的字符多重集相同当且仅当它们排序后的结果相同。tea排序后是aetate排序后是aettan排序后是ant所以aet就成为了tea、ate、eat这一组异位词的公共标识而ant则是tan、nat这组的标识。不同组之间排序结果各不相同。这个性质看起来简单其实是整道题的基石。面试官追问“为什么不能把原字符串当key”时你可以回答原字符串只是多重集的一个随机排列不是唯一表示只有排序后的结果才与多重集一一对应。2.2 核心代码与写法说明Python版本最简洁from collections import defaultdict from typing import List class Solution: def groupAnagrams(self, strs: List[str]) - List[List[str]]: mp defaultdict(list) for s in strs: key .join(sorted(s)) mp[key].append(s) return list(mp.values())Java版本稍微啰嗦一点但逻辑完全一样class Solution { 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()); } }两段代码的核心动作都是三件事生成签名、查桶、入桶。Python里defaultdict(list)可以省去判断key是否存在的步骤Java里computeIfAbsent也能达成同样的效果比先get再put少写好几行。我这里额外提醒一句return list(mp.values())返回的列表顺序取决于HashMap的遍历顺序不是strs的原始插入顺序。题目要求返回任意顺序所以没问题。但如果你自己写预案时对顺序有要求后面要手动排序。2.3 时间复杂度推导别背答案设字符串数组长度为n字符串平均长度为k。对每个字符串执行一次排序排序平均时间复杂度是O(k log k)n个字符串合计就是O(n * k log k)。哈希表的插入和查找在平均情况下都是O(1)主循环的总复杂度就是O(n * k log k)。空间复杂度方面HashMap需要保存所有字符串的引用和对应的key最坏情况下是所有字符串都两两异位需要存n个不同的key和n个字符串引用所以空间是O(n * k)。补充一个工程视角排序的时间并不是固定的。当字符串很短时比如长度只有3到5个字符Sort的常数很小当字符串很长时比如长度上千排序的开销就会变成主要矛盾。这也是为什么后面要聊计数法——它绕开了排序直接用频次统计作为签名对长字符串更友好。2.4 写排序法时的三个细节我见过不少人在细节上踩坑这里集中说三个。第一个是Python里.join(sorted(s))的返回值。sorted(s)返回的是一个字符列表比如[a, e, t]必须用join拼回字符串才能当哈希key。直接拿列表当key会直接报TypeError: unhashable type: list。第二个是Java里一定要用new String(arr)而不是arr.toString()。数组的toString()返回的是类似[C5e2de80c的对象地址字符串不是数组内容。排序后如果直接用arr本身当key也不行Java数组的hashCode基于对象地址两个内容一样的数组哈希值不同分桶就全乱了。第三个是C的注意点。如果你用std::string做key需要先复制一遍字符串再原地sort因为sort会修改原字符串。我见过有人直接sort(s.begin(), s.end())然后拿s当key结果原数组的字符串全部被覆盖输出时发现所有元素都变成了排序后的形式。3. 解法二计数签名法不排序也能分3.1 思路26维频次向量既然判断异位词本质是判断“每种字符出现的次数是否相同”那为什么不直接把频次统计结果本身当签名呢对于仅包含小写字母的输入可以开一个长度为26的数组cnt遍历字符串每遇到一个字符就把对应位置加1。这样每个字符串都对应着一个长度为26的频次向量比如eat -[1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, ...]a、e、t各1次tea - 同样的向量ate - 同样的向量这个向量就是一个签名。两个字符串是异位词当且仅当它们的频次向量完全相同。从数学角度看这个签名其实就是“多重集的直方图表示”用一个固定维度的向量把字符分布完整记录下来。排序法是把多重集变成“有序序列”计数法是把它变成“频次分布”殊途同归。3.2 键值设计的经典陷阱数组转字符串要加分隔符想法很简单实现时有个坑非常隐蔽不能直接把数组转成字符串当key否则会产生误判。假设cnt数组是[1, 11, 0, 0, ...]如果直接.join(map(str, cnt))得到的是111000...。另一个数组[11, 1, 0, 0, ...]转成字符串也是111000...。两个完全不同字符分布的单词签名却一样这会导致本不该分组的字符串被错误地放进同一个桶里。这就是经典的“序列化边界混淆”问题——数字之间没有分隔符拼接后信息就丢失了。解决办法有两个方案一Python里直接用tuple(cnt)当key。元组是可哈希的且逐元素比较不会有歧义。key tuple(cnt) mp[key].append(s)方案二转字符串时加入分隔符。Java里我习惯用#拼接每个数字StringBuilder sb new StringBuilder(); for (int i 0; i 26; i) { sb.append(cnt[i]).append(#); } String key sb.toString();这样[1, 11, 0, ...]会变成1#11#0#...[11, 1, 0, ...]会变成11#1#0#...两者不再混淆。这个坑在面试中经常被当作考察细节的追问点答出来会很加分。3.3 两种语言的完整实现Python推荐用tuple当key代码相当简洁from collections import defaultdict from typing import List class Solution: def groupAnagrams(self, strs: List[str]) - List[List[str]]: mp defaultdict(list) for s in strs: cnt [0] * 26 for ch in s: cnt[ord(ch) - ord(a)] 1 mp[tuple(cnt)].append(s) return list(mp.values())Java的写法class Solution { public ListListString groupAnagrams(String[] strs) { MapString, ListString map new HashMap(); for (String s : strs) { int[] cnt new int[26]; for (char c : s.toCharArray()) { cnt[c - a]; } StringBuilder sb new StringBuilder(); for (int i 0; i 26; i) { sb.append(cnt[i]).append(#); } String key sb.toString(); map.computeIfAbsent(key, k - new ArrayList()).add(s); } return new ArrayList(map.values()); } }这段代码有一个细节值得说Java里int[]不能直接作为HashMap的key因为数组的equals和hashCode都是基于对象引用的内容相同但引用不同的数组会被当作不同的key。所以必须把数组序列化成字符串或者用ListInteger包装。ListInteger理论上可以做key但每次生成都会产生大量包装对象内存开销大不如字符串方案干净。3.4 排序法和计数法到底怎么选两种方法都能过题但适用场景不同。维度排序签名法计数签名法核心操作对每个字符串排序遍历统计频次再序列化向量单字符串时间复杂度O(k log k)O(k 字符集大小)总时间复杂度O(n · k log k)O(n · (k |Σ|))依赖字符集大小不依赖通用依赖小写字母用26全字符需扩展代码复杂度最简单稍复杂注意序列化细节长字符串场景排序成本高更占优短字符串场景常数小通常最快同样很快差别不大实际建议面试优先写排序法因为代码短、思路好解释、还不容易在序列化上犯错。如果面试官追问“字符串特别长怎么办”再切换到计数法说明你理解两种方案的取舍。刷题不需要追求最优能完整讲清楚trade-off往往比秒写出最优解更加分。4. 解法三质数乘积法有趣的脑洞与工程现实4.1 数学基础算术基本定理除了排序和计数圈子里还流传着一种“神仙解法”给26个小写字母分别分配一个质数比如a2b3c5d7e11f13……然后每个字符串的签名就是所有字符对应质数的乘积。判断依据是算术基本定理任何正整数都能唯一地分解为质数的乘积。两个字符串的质数乘积相同当且仅当它们包含的质数因子的集合和数量一致也就是字母的频次一致。乘法满足交换律所以字母顺序无关紧要——这正好符合异位词的定义。举个例子假设a2、e11、t71eat的签名是2 × 11 × 71 1562tea是71 × 11 × 2 1562ate是2 × 71 × 11 1562。三者的乘积完全一致直接落到同一个桶里。这套思路非常漂亮尤其适合用来理解“数学映射”在算法设计中的美感。我甚至在一次团队分享里用它当例子说明如何把一个离散问题转化为数值问题。4.2 算一算就发现的问题但漂亮归漂亮实际工程里几乎没人这么写原因很简单数值爆炸。质数乘积随字符串长度呈指数增长。随便估算一下如果字符串是10个字母每个字母对应的质数取26个质数中偏大的101那么乘积就是101^10大约1.1 × 10^20已经超过Java long的表示范围约9.2 × 10^18。即便字母都用较小的质数比如取前10个质数乘积也是2×3×5×7×11×13×17×19×23×29 6469693230约64亿Java int根本存不下long勉强能扛。那用BigInteger行不行行但性能代价很大。程序里每个字符串都要做一次大整数乘法字符串一长大整数运算的时间开销和内存占用都会显著增加。LeetCode的测试用例中字符串长度可能达到数千质数法在极端数据下会退化得很严重。所以我的结论是质数法适合作为思维拓展和面试谈资真正写代码还是用排序法或计数法。4.3 从质数法看哈希冲突的本质虽然质数法不能用于生产但它意外地适合用来理解哈希表冲突。哈希表的key本质上是把无限的对象空间映射到有限的值空间。质数法是“理论上零冲突”的映射但代价是数值空间无限膨胀。工程上的哈希函数则相反努力把值空间压缩到固定范围比如32位整数但压缩必然意味着不同对象可能映射到相同值这就是冲突。解决冲突需要桶内再做一次完整比较这也是HashMap为什么除了比较哈希码还要用equals确认对象真的相等。回到这道题如果某个人用质数法或自定义哈希值做key他仍然需要二次确认两个字符串是否真的是异位词而不能只看哈希值。这个逻辑和HashMap的设计如出一辙。5. 实战视角边界情况与面试追问实录5.1 提交前先过一遍边界清单代码写完了先别急着交。LeetCode的隐藏测试用例里常埋着一些边界条件我自己至少在这几个case上翻过车空字符串数组应该直接返回空列表两种解法天然支持不会额外处理。只有一个空字符串[]空串排序后还是空串计数法统计全为0会落到自己的桶里输出[[]]。单个字符如[a, b]]排序后分别为a和b计数法频次向量不同能正确分开。全部字符串互为异位词如[ab, ba, ab]结果应该是一个桶装3个字符串。这里要确保map的value用的是List而不是Set否则重复的ab会被去重。字符串本身重复[a, a, b]输出[[a, a], [b]]分组时要保留重复元素。这些case虽然简单但它们能检验你的代码是否把“分组”和“去重”混为一谈。List是分组Set才是去重。5.2 Java、Python、C里的语言级陷阱编程语言的细节会直接影响解法实现这里把几个典型问题集中说一遍。Python中list不可哈希所以cnt数组不能直接当key必须转成tuple。tuple(cnt)生成的是一个新的元组对象可哈希、内容可比较这是Python里最顺手的做法。Java中int[]和char[]的equals都是引用比较内容一样也不相等所以不能直接当key。Arrays.asList生成的List虽然能用但里面全是包装对象每个字符串都要建一堆Integer对象内存和CPU都有开销。更干净的方式是把数组序列化成字符串。C中vectorint可以作为unordered_map的key但前提是你自己提供哈希仿函数标准库没有为vectorint提供哈希特化。如果不想写哈希仿函数最省事的方法仍然是排序后转成string。这些细节在面试里都是“加分题”。你不需要背下来但至少要知道自己的语言在这个场景下有哪些限制以及为什么别人的代码里要用某种写法绕开这些限制。5.3 面试官常问的三个follow-up这道题在面试中经常被追问我梳理了三个出现频率最高的问题。第一个“如果有上百万个字符串内存放不下怎么处理”这其实是一个分布式/外部排序问题。可以先按字符串长度分桶长度不同的一定不是异位词这样能把数据打散到不同的分区每个分区内部再用签名法分组如果分区仍然很大还可以用类似MapReduce的思路把“排序后的字符串”作为shuffle的partition key天然完成分组。第二个“如果输入不只是小写字母而是全量Unicode字符计数法还适用吗”直接开数组就不行了需要改用HashMapCharacter, Integer统计频次再序列化整个map作为key。不过这种写法的序列化成本较高此时排序法可能是更简洁的降级方案因为它完全不依赖字符集大小。第三个“如果要求每个桶内部的字符串按字典序输出怎么办”分组后对每个List调用一次排序就行。复杂度会额外增加O(n log n)但最坏情况下所有字符串都在一个桶里排序成本会比较高。如果对输出顺序有预先要求也可以在分组前先对整个数组排序再按签名分组这样每组内部天然有序。面试官问这个主要是考察你能否区分“分组的无序性”和“组内有序性”两个不同需求。6. 举一反三异位词这个知识点还能怎么考6.1 同族题目的套路总结“字母异位词分组”真正的价值在于它的解题框架能直接迁移到好几道经典题目上。LeetCode 242“有效的字母异位词”就是简化版只需要判断两个字符串是否为异位词。我习惯用计数法先统计第一个字符串的频次再遍历第二个字符串递减频次最后检查计数数组是否全部为零。这比排序法更快而且可以作为“字母异位词分组”的前置热身题。LeetCode 438“找到字符串中所有字母异位词”稍微进阶要求在一个长字符串中找到目标串的所有异位词子串的起始位置。核心思路从“静态分组”变成“滑动窗口快照”窗口内统计频次每次右移一位左侧移除一个字符右侧加入一个字符判断当前的频次向量是否和目标串的频次向量一致。这其实是“计数签名法”在动态窗口上的延伸。如果把这组题连起来刷一遍你会发现自己反复使用的都是同一个能力把一个状态静态字符串或滑动窗口映射成一个可比较的签名然后判断签名是否相同。这个能力在做字符串类题目时非常通用。6.2 签名思想在工程场景的迁移这道题从LeetCode走向生产环境最常见的例子是数据去重和日志聚类。比如清洗几千万条重复日志时如果把每条日志的完整文本作为key内存根本扛不住。更聪明的做法是先计算一个紧凑的签名比如哈希值或归一化后的文本骨架用签名做初步分组签名相同的日志再进行精确比对。这和本题“签名 桶”的框架完全一致。再比如做文件的相似度检测可以先提取文件内容的特征向量比如词频直方图用向量签名分组再在组内做细节比对。数据库里对两个文本字段做“是否只是顺序不同”的校验本质上也是异位词判断的工程版。刷题刷到最后你会发现很多题目模型就是工程问题的微缩版。6.3 怎么把这题的价值榨干最后聊点刷题方法论。我个人觉得LeetCode hot 100里这道题不算难但它特别适合用来练“从题目到解法”的推导能力。拿到一道新题先不要急着写代码而是问自己三个问题这个任务到底在判断什么有没有办法把所有输入归一化为一个标准形式这个标准形式能否作为哈希表的key按这个流程走一遍“字母异位词分组”就是从“判断多重集是否相等”自然推导出“排序签名”或“频次签名”这两个方案。我踩过不少次坑之后的一个体会是刷题提升最快的部分不是记题解而是养成“签名化”的思维习惯。当你看到一个需要分类、分组、判重的题第一反应是“这些东西的共同签名是什么、怎么生成一个低冲突高可比的key”那这道题就不只是过了而是真正变成了你自己的解题能力。