前两天帮一个准备跳槽的朋友过LeetCode高频题，刷到第49题“字母异位词分组”时，他三分钟写出了排序法，却答不上来“为什么计数法更适合超长字符串”这种追问。这个画面我见过太多次——题目本身不难，但大多数人在背解法，没吃透“异位词”背后的签名思想。借着这篇分享，我打算把这道题从题意、三种解法、复杂度分析到工程落地完整拆一遍。适合两类人看：一类是正在准备算法面试、想把高频题刷透的同学；另一类是在业务里做文本归一化、重复数据识别的工程师。因为字母异位词分组不只是一道题，它抽象出来就是“给一组字符串找一个稳定的规范化签名，再按签名聚类”，这个能力放到商品标题去重、变体文本风控里同样成立。先把这个题最底层的需求拆明白。

1. 这道题到底在考什么：字母异位词的前世今生

1.1 从题目描述出发，画清楚边界

所谓字母异位词，就是字母组成完全相同、只是排列顺序不同的字符串。最经典的例子是eat、tea、ate这三个词，字母集合都是{a, e, t}，各自出现次数也完全一样，所以它们互为异位词。而tan和nat又是一组，字母集合是{a, n, t}。bat和前面的词共享a和t，但多了一个b，少了e或n，所以不能混进前面任何一组。

题目给一个字符串数组，要求把所有互为字母异位词的字符串放进同一个列表，最终返回一个二维列表，每一组内部的顺序、以及各组之间的顺序都不限制。边界条件很容易被忽略：数组可能为空，结果是[]；数组里可能有空字符串，多个空字符串应该归到同一组；也可能有大量重复字符串，比如 50 个"abc"，它们同样要待在一个桶里。

一个容易混淆的细节：题目默认输入只包含小写字母，所以处理时可以直接用ord(ch) - ord('a')映射到 0 到 25。如果面试官没有明确说，你可以在解法里补一句“我按题目约定，输入为小写字母”，这样既严谨，又给后面的扩展讨论留了话口。

1.2 为什么它值得反复刷

这道题是哈希表应用里的“样板题”，核心考点只有两个：第一，识别异位词的不变量；第二，设计一个合适的哈希键。所谓不变量，指的是无论字母怎么重排，每个字母出现的次数不会变。换句话说，eat变成tea，只是位置换了，频次表依然是一份a:1, t:1, e:1。抓住这个不变量，所有解法都围绕同一件事展开：把“无法直接比较的字符串”转换成一个“规格化的签名”，再以签名为键做聚合。

这也是为什么这道题被各大厂反复翻牌。一个面试者如果只会写排序法，说明基本能力过关；如果能主动说出计数法、分析两种方案的复杂度差异，说明对哈希键的设计有理解；如果再能把质数乘积的数学思路拿出来当彩蛋，同时指出其工程隐患，那基本就站在了第一梯队。

从工程视角看，这道题的价值更直接。我在做数据清洗时遇到过商品标题去重，很多卖家会把“三文鱼刺身”改成“刺身三文鱼”重新铺货，肉眼一看就是同一件商品，但字符串直接比对怎么都对不上。后来用的方案，本质上就是字母异位词分组的思路，只不过把“字母”换成了“词”。因此这题值得反复刷，而且刷的时候最好带着“这套签名逻辑能搬到哪”的思考去理解。

2. 解法一：排序字符串当哈希键，最直观也最容易被面试官追问

2.1 思路一句话，代码八行

如果把一个字符串内部的字母按字典序排好，异位词就会得到同一个结果。比如eat、tea、ate排序后都是aet，tan和nat排序后都是ant。这样排序后的字符串就成了一种规范化签名，直接作为哈希表的键，原字符串作为值塞进对应列表。

from collections import defaultdict def group_anagrams(strs): groups = defaultdict(list) for s in strs: key = "".join(sorted(s)) groups[key].append(s) return list(groups.values())

核心就一个操作："".join(sorted(s))。这里有个新手必踩的坑——sorted(s)返回的是字符列表，比如['a', 'e', 't']，而列表在 Python 里不可哈希，没法直接当字典的键，必须先join成字符串。很多人在白板上写key = sorted(s)，一运行就报TypeError: unhashable type: 'list'，然后整个人懵掉。

如果面试官要求你写其他语言，思路完全一致。Java 版用char[]排序后new String即可：

public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> map = new HashMap<>(); for (String s : strs) { char[] chars = s.toCharArray(); Arrays.sort(chars); String key = new String(chars); map.computeIfAbsent(key, k -> new ArrayList<>()).add(s); } return new ArrayList<>(map.values()); }

这段代码同样简洁，核心也是“排序产生签名”。注意 Java 里Arrays.sort是对字符数组原地排序，排序结果转回字符串时，用new String(chars)而不是chars.toString()，后者拿到的只是对象地址字符串，这是另一个高频低级错误。

2.2 复杂度分析与排序的代价

设一共有n个字符串，每个字符串平均长度是k。对单个字符串排序的时间复杂度是O(k log k)，最坏情况下所有字符串都处理一遍，总时间复杂度就是O(n * k log k)。空间上，哈希表每个键平均长度为k，每个原字符串都要存进结果，因此空间复杂度是O(n * k)。

这里有一个容易被面试官追问的细节：字符串排序比较两个字符并不是 O(1) 吗？为什么单个字符串排序是O(k log k)而不是O(k)？因为基于比较的排序需要执行k log k次字符比较，每次比较才 O(1)，所以总代价确实是O(k log k)。如果继续较真，Python 的 Timsort 在部分有序输入上会更快，但平均意义下就是这个复杂度。

排序法最大的优点是好写、好读、不容易出错。面试时作为首个方案非常合适，因为你可以迅速写出干净代码，再把剩余时间用在方案演进上。它的缺点是当k很大时，排序开销会明显放大。假设有 10000 个长度 1000 的字符串，10000 * 1000 * log2(1000)大约是 1 亿次级别操作，计数法会更有优势。但如果只是普通英文单词，k通常在 5 到 10 之间，排序法的常数小，实际跑起来并不慢。所以面试里说“排序法在短单词场景下足够好”，不是借口，是事实。

3. 解法二：字符计数表当哈希键，理论上更优

3.1 用 26 位频率数组给字符串“指纹”

既然异位词的核心不变量是“每个字母出现次数”，那就可以不排序，直接统计频次。小写字母只有 26 个，开一个长度 26 的整数数组，遍历字符串，每遇到一个字符就在对应位置加 1。统计完成后，把这个数组转成不可变的哈希键。

from collections import defaultdict def group_anagrams(strs): groups = defaultdict(list) for s in strs: count = [0] * 26 for ch in s: count[ord(ch) - ord("a")] += 1 groups[tuple(count)].append(s) return list(groups.values())

这里的关键是tuple(count)。列表count本身可变且不可哈希，但转成元组之后，内容相同的元组在 Python 中是相等的，也会得到相同的哈希值。比如eat和tea统计出来的都是(1, 0, 0, 0, 1, ..., 1)（位置 0 是a，位置 4 是e，位置 19 是t），因此会进入同一个桶。

Java 版通常不用 List 做键，而是拼成一个带分隔符的字符串，避免歧义：

public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> 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 c : count) { sb.append('#'); sb.append(c); } map.computeIfAbsent(sb.toString(), k -> new ArrayList<>()).add(s); } return new ArrayList<>(map.values()); }

拼接时加#是为了防止连续数字串歧义。如果不加分隔符，[1, 12]和[11, 2]都会拼成"112"，导致两个不同的频次表撞到同一个键，这属于工程实现里极高的低级错误，但白板题里很容易被忽略。

3.2 边界条件与实现细节

空字符串的统计数组是全 0，tuple([0] * 26)作为键，所有空字符串自然归为一组。这一点比排序法更隐式——排序法里""作为键也正常，但如果你用某些语言写排序字符串，空串排序后还是空串，不会出错，只是面试的时候要记得提一句“空字符串也能正常分组”，体现边界意识。

如果输入包含大写字母，ord(ch) - ord('a')会算出负数或超过 25 的下标，直接越界。工程中一般先做规范化：

s = s.lower()

如果字符集不是 26 个英文字母，而是包含数字、空格、中文、表情符号，固定数组就不够用了。更通用的做法是用collections.Counter：

from collections import Counter def group_anagrams(strs): groups = defaultdict(list) for s in strs: counter = Counter(s) key = frozenset(counter.items()) groups[key].append(s) return list(groups.values())

Counter本身不可哈希，但frozenset(counter.items())把键值对冻结成集合，就可以作为哈希键。要注意的是，frozenset不区分字母顺序，同一字符频次会合并，正好符合需求。这个方案在处理中文时也同样适用，比如“你好”和“好你”会被分到同一组。但是在真实中文语境里，词序变化经常导致语义改变，是否要按异位词聚类，取决于业务目标，这一点第 7 节会展开。

计数法的时间复杂度是O(n * k)，因为每个字符串只需遍历一次统计频次，再固定遍历 26 个位置生成键，总代价是O(n * (k + 26))，按大 O 记法就是O(n * k)。空间上每个键的长度固定为 26，整体依然是O(n * k)。相比排序法，它把log k换成了常数的 26，在超长字符串场景下优势明显。

4. 解法三：质数乘积与更多奇技淫巧，能聊但不能当主答案

4.1 质数映射的思路

用质数乘积给异位词做哈希，是面试里很有意思的“加分项”。思路是：把 26 个小写字母分别映射到一个质数，比如a -> 2, b -> 3, c -> 5, d -> 7, e -> 11，依此类推。然后一个字符串的签名就是所有字符对应质数的乘积。由于质因数分解的唯一性，两个字符串乘积相同，当且仅当它们包含的字母及频次完全相同。

from collections import defaultdict PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101] def group_anagrams(strs): groups = defaultdict(list) for s in strs: product = 1 for ch in s: product *= PRIMES[ord(ch) - ord("a")] groups[product].append(s) return list(groups.values())

数学上非常优美，乘法满足交换律，所以字母顺序不影响结果。而且不需要再处理字符数组排序、也不需要生成 26 个数字的序列，代码看起来甚至比前两种更短。空字符串的乘积是 1，多个空字符串会归组，行为正确。

4.2 为什么工作里不推荐

但你要是真把这套方案写到生产代码里，我会劝你三思。第一个问题是溢出：字符串稍微长一点，比如 40 个字母，乘积就可能达到几十位数字。Python 的大整数能扛住，Java 的long会直接溢出，必须换成BigInteger，性能和内存双双恶化。第二个问题是可读性：你没法从19399380这个键反推它代表什么字母组合，将来排查数据问题，根本不知道键长什么样。排序法和计数法生成的键要么让人一眼看懂，要么可以快速转回频次表。

所以质数乘积的正确用法是：作为面试尾声的思维拓展彩蛋，展示你理解哈希设计的数学本质。面试官问“还有没有别的思路”时提一嘴，反而加分。主动拿它当主解法，尤其是在 Java 面试里写BigInteger，大概率会被继续追问溢出问题，然后陷入不必要的解释。我在实际指导别人刷题时，经常说一句话：解题最优不一定等于面试最优，面试最优也不一定等于工程最优，这三个“最优”经常是三套选择。

5. 三套方案对比与选型指南

5.1 时间与空间复杂度汇总

把前面三套方案放到同一张表里对比，看起来更直观。

这里有一个容易误解的空间复杂度：三套方案的结果数组占了O(n * k)，这部分无论如何都省不掉，因为题目要求返回全部分组。哈希表本身存储键的额外开销则不同，排序法的键平均长度为k，计数法的键固定为 26，质数法的键是一个大整数，实际占用随字符串长度增长而增长。但在理论大 O 级别上三者都是O(n * k)，所以面试时先答出这一层就够了。

如果面试官追问“计数法理论上更快，为什么你首选排序法”，可以这样回答：对于普通英文单词，k很小，log k几乎可以忽略；排序法代码更简单、键更容易调试；当数据中出现超长字符串时，再切换到计数法。这种“根据输入特征选择方案”的思维方式，比只背一种解法更能体现工程素养。

5.2 不同数据形态下的选型建议

在实际开发里，选型不该只看算法复杂度，还要看数据形态和排查成本。我给一个自己常用的决策规则：

• 输入是英文短语、商品标题、日志关键词，长度基本不超过 50，优先排序法。理由很简单：出问题好查。你看到一个键是"aet"，马上能想明白它来自eat，但看到一个键是(1, 0, 0, ...)或19399380，还得再转换一下。
• 输入是 DNA 序列、基因片段、超长字符串，长度可能上千，优先计数法。排序一次 1000 字符的字符串，代价明显比统计 26 个频次高。
• 输入包含中文、多语言、emoji，固定 26 维数组失效，用Counter加frozenset的扩展方案。
• 数据规模大到放不进单机内存，上述所有单机方案都不够。需要走分布式框架，比如 Spark 里对每个字符串生成签名后做groupBy(sign)，本质上是排序法思想，把“本地哈希表”换成了“分布式 Shuffle”。这时候算法本身没变，瓶颈转移到了网络 IO 和倾斜 key 的处理上。

这个决策规则我用了很多年，最大的教训是：不要为了理论上的一点性能提升，牺牲可调试性。线上系统出问题，能 5 分钟定位到键的含义，比省那几毫秒重要得多。

6. 刷题现场：从笔试到面试的常见坑

6.1 我踩过的五个经典坑

先说我自己的黑历史。第一次写这题用的 Python，key = sorted(s)直接当字典键，报错后我盯着TypeError看了半分钟，才反应过来要join。这种低级错误在面试高压环境下特别容易犯，所以我现在教人，一定会把“排序返回列表、列表不可哈希”这句话反复强调。

第二个坑来自 Java。int[]数组在 Java 里是基于引用相等做哈希的，直接拿数组当HashMap的键，每组值都是 1。更隐蔽的是Arrays.asList(count)也不能用，因为它是List<int[]>，里面元素还是数组。正确的做法是拼接为字符串，或者用List<Integer>转包装类。

第三个坑是空字符串。很多人把if not s单独处理成一组，但实际上多个空字符串都应该在同一组。正确的键是空串或者全 0 元组，默认让它们自然归组即可，不需要写分支。

第四个坑是大规模重复字符串。比如输入是 10000 个"abc"，排序法会对每个"abc"都排一遍。功能上没问题，但如果你在追求极致性能，可以在排序前查一下缓存，或者先用Counter统计原字符串出现次数，对去重后的字符串做分组，最后再乘上次数生成结果。不过面试时并不需要主动做这个优化，提一句“可以缓存高频键”就能体现思考深度。

第五个坑是输入规范化。有些题解默认字符串只含小写字母，但实际笔试里可能出现"Eat"和"eat"混在一起。我的习惯是写解法前先确认输入约束，如果没说明，就在代码开头加s = s.lower()，并去掉空格和标点（如果要处理的话）。这个动作本身不复杂，却能避免大量边界问题。

6.2 测试用例清单，直接拿去用

刷题时我习惯准备一组固定用例，本地一跑，能覆盖大部分边界。下面这份清单可以直接复制到你的测试文件里。

我实际跑这些用例时发现，最容易挂的是["", ""]这一条。很多人会忘记空字符串也要分组，或者手动用if s == "": return [[""]]处理成错误结果。如果你写的排序法或计数法，空字符串自然产生同一个键，默认行为就是正确的，不需要特判，这反而说明“让不变量自然生效”比手动逻辑分支更可靠。

7. 视角放大：字母异位词分组在工程里的真身

7.1 同义归一化与数据清洗

字母异位词分组的底层思想是“签名归一化”。在真实业务里，这个思想最常见的落点是数据清洗。举个例子，跨境电商平台经常有卖家重复铺货，把同一个商品标题里的词序打乱，比如Organic Coconut Oil 500ml和Coconut Oil 500ml Organic，平台如果不做处理，搜索引擎会把它们当成两个不同的商品。

处理流程和 LeetCode 题几乎一一对应：先把标题统一转小写，去掉标点符号，把字符串内部字符排序或者按“单词”排序，生成一个签名，然后用这个签名做group by或reduce。按字符排序适合短文本，按单词排序更适合英文标题，因为它能保留词边界，coconut oil和oil coconut会拿到同一个签名，而ococonutil这种字符级签名没法再还原回可读文本。

在数据库层面，可以给表增加一列normalized_key，写入时同步生成并建索引。后续查重直接用GROUP BY normalized_key HAVING COUNT(*) > 1就能找出重复标题。这种冗余列方案最大的好处是查询走索引，不需要对全表做实时计算。很多数据仓库建模里的“拉链表”“维度表”，本质也是这种“增加规范化签名字段”的思路。

7.2 文本指纹与风控场景

另一个偏工程的方向是文本指纹。我在做风控相关需求时，会用它识别批量变体文本。比如灰产用户为了绕过关键词屏蔽，把“优惠券”写成“券优惠”，把“进群加我”改成“加我进群”，字面上是同一个字符集合，字母异位词的签名完全一样，可以直接作为召回特征。

但这里要提醒一句：字符重排并不等于语义相同，尤其在中文场景。“北京欢迎你”和“你欢迎北京”是异位词，但意思完全不同。如果直接按字母异位词分组去处罚用户，误杀率一定很高。工程上正确做法是把它当作候选召回手段，先用签名聚拢一批可能相关的文本，再用真正的语义相似度模型做精排。我在实际项目里得到的比例大概是：签名召回可以覆盖掉 70% 以上的恶意变体，但最终确认违规还需要人工或模型复核。

这个模式其实和解算法题很类似：先用一个低成本的“不变量”把数据分桶，再用更高成本但更准确的逻辑处理桶内内容。字母异位词分组就是那个低成本分桶器的教科书版本。理解了这层，再看 LeetCode 题，你不会只觉得它是“哈希表练习”，而会看到一套可迁移的工程设计方法论。

最后说点个人体会。刷这个题最有价值的收获，不是背下某一种解法，而是养成“寻找稳定签名”的思维习惯。我在实际代码里最常用的还是排序签名，因为它让结果可读、可查、可解释；只有当单条文本真的很长时，才会换计数方案。如果你也写过类似的分组逻辑，不管是处理商品标题还是识别文本变体，欢迎在评论区说说你用的“签名方案”。下一题我准备聊聊 Top K 系列，那个方向和大数据面试结合得更紧。