1. 先把“字母异位词”这道题翻译成人话1.1 anagram的准确定义与题目原貌刷题圈有个老段子跟不刷题的朋友提“字母异位词”对方多半愣住换成“就是字母重新排列”他马上点头。所谓字母异位词anagram指的是两个字符串包含的字符种类和数量完全相同只是排列顺序被打乱了。比如 listen 和 silentrace 和 careastronomer 和 moonstarer都是教科书级的例子。LeetCode 49 的原题叫 Group Anagrams中文翻译成“字母异位词分组”。题面不长给定一个字符串数组 strs要求把所有互为字母异位词的字符串放进同一个组里返回一个二维数组分组顺序和组内顺序都不要求固定。官方示例长这样输入strs [eat,tea,tan,ate,nat,bat]输出[[bat],[nat,tan],[ate,eat,tea]]里面 eat、tea、ate 三个词都是由一个 e、一个 a、一个 t 组成的所以被分到一起tan 和 nat 由一个 t、一个 a、一个 n 组成分到一起bat 的字符组合独一无二只能自己单成一列。这道题在主流大厂面试里出现频率极高经常被拿来当热身题或者二面的开场题。它本身不难但含金量不低如果只是背答案你顶多记住一种写法真正把它吃透应该理解背后那两条核心思路——用排序后的字符串做键、用字符计数做键。这两条思路理解了类似的“变位词判断”“同义词归并”“字符乱序匹配”问题基本都能顺手解掉。1.2 分组为什么比“判断两个词是否异位词”难一截如果题目只是问“s 和 t 是不是异位词”解法非常直接把两个字符串分别排序后比较或者各自扫一遍做字符计数再比较。这是典型的“两两比较”问题逻辑清晰没什么好纠结的。但改成“分组”之后很多人第一反应还是回到两两比较拿第一个字符串当基准往后挨个比比出来的放一组比完再换下一组。思路没错实际跑起来却非常勉强。n 个字符串两两组合是 O(n²) 次比较每次比较还要排序或计数整体复杂度一下子就难看。更麻烦的是当出现三个以上互为异位词的字符串时用这种“先固定一个再往后找”的策略代码里很容易搞出重复分组或者漏分的情况调试起来特别耗时间。这道题真正想考察的东西其实就一句话你有没有“先给一类东西找一个规范形再利用哈希表聚合”的意识。我理解的规范形canonical form是这个意思一堆对象想放进同一个桶里你得先找到一个只跟“类别”有关、跟“个体差异”无关的表示。对异位词来说同组内个体之间唯一可能不同的地方就是字符顺序。那么只要把顺序这个信息消掉剩下的东西就能代表整个类别。消掉字符顺序最自然的两条路一条是把字符强行排成固定顺序另一条是把每个字符出现的次数记下来。排成固定顺序就是下文要说的排序键记次数就是计数键。这两个模型掌握之后LeetCode 49 这道题的参考答案其实已经在你脑子里了。2. 排序键把所有字符串归一到同一个规范形2.1 排序结果能当钥匙依赖一个简单但关键的恒等关系先想一件事字符串 s 被排序之后得到的结果是什么是它的字符多重集按顺序排列后的样子。所谓多重集就是只关心“有哪些字符、各多少个”完全不关心先后顺序。两个字符串互为异位词当且仅当它们的字符多重集相同也当且仅当它们排序后的字符串完全一样。这个恒等关系是整个排序键方案的基石。排序这个操作把 eat、tea、ate 全都变成 aet于是它们在哈希表里自动落到同一个 key 上tan 和 nat 排序后都变成 ant自然落到另一个 key 上bat 排序后是 abt谁也搭配不上单独成组。排序键还有一个重要性质无碰撞。两个不同的异位词类排序结果必然不同。因为排序结果唯一地刻画了原字符多重集多重集不同排序结果就不可能相同。这听起来像句废话但它保证了哈希表的 key 之间不会互相侵占答案天然正确。面试时如果被追问“为什么想到用排序”可以从这个角度回答我希望同组字符串经过某个变换后变成完全相同的字符串排序是最直接的手段因为排序结果本质上就是字符多重集的规范形。2.2 Python实现与JavaScript实现先给一个最常用、最容易读的 Python 版本from collections import defaultdict def group_anagrams(strs: list[str]) - list[list[str]]: groups defaultdict(list) for s in strs: key .join(sorted(s)) groups[key].append(s) return list(groups.values())核心逻辑只有四行但有几个细节值得说明。sorted(s)在 Python 中会把字符串拆成字符列表再排序排完还是一个列表不能直接当字典键所以必须用.join(...)拼回字符串。初学者在这里特别容易翻车忘了 join直接把一个 list 拿去当 key运行到groups[key]时立刻报错 TypeError: unhashable type: list后面第 4 节我会专门展开这类提交事故。defaultdict(list)的作用是自动初始化一个空列表省掉“判断 key 是否存在”的样板代码。不喜欢 defaultdict 的同学可以这样写完全等价groups {} for s in strs: key .join(sorted(s)) groups.setdefault(key, []).append(s)返回list(groups.values())时Python 3.7 的字典会保留插入顺序所以输出顺序基本上按照“第一次在数组里遇到某个分组 key”的顺序来。题目不要求这个所以不用管。JavaScript 版本同样简洁function groupAnagrams(strs) { const groups new Map(); for (const s of strs) { const key [...s].sort().join(); if (!groups.has(key)) groups.set(key, []); groups.get(key).push(s); } return [...groups.values()]; }这里有个习惯问题[...s]和s.split()都能把字符串拆成数组但前者按 Unicode 码点拆分后者按 UTF-16 码元拆分。遇到 emoji 或者生僻字时split()会把一个字符拆成两半导致排序结果错乱。虽然 LeetCode 这道题只输入小写字母用split()也能过但养成使用展开运算符的习惯写别的字符串处理逻辑时能少踩很多坑。2.3 边界条件与复杂度推演题目并没有保证字符串长度大于 0所以空字符串是合法输入。空字符串排序后还是空字符串因此所有空串都会归到 key 为 的同一个分组下面不存在问题。单字符字符串也同理a 排序后还是 a它跟由其他字符组成的字符串不会发生碰撞。如果输入的数组里有重复字符串比如两个 bat它们会出现在同一个分组里组内重复出现两次。这是题目允许的不要试图去重。时间复杂度的推导是面试中绕不开的一环。设 strs 长度为 n最长字符串长度为 k每个字符串执行一次排序耗时 O(k log k)排序后还要做一次 join耗时 O(k)哈希表插入和更新的均摊复杂度是 O(k)因为要比较和存储字符串总时间复杂度 O(n·k log k)。空间方面哈希表里存储了全部 n 个字符串每个字符串长度不超过 k所以至少 O(n·k) 的空间。排序键本身也需要存储每个 key 的长度等于对应分组里字符串的长度极端情况下所有字符串互不为异位词就会有 n 个平均长度为 k 的 key额外空间也是 O(n·k)。面试时说“空间复杂度 O(n·k)”不会出错。3. 计数键用固定的26维向量替代排序3.1 为什么计数数组也是同一件事的另一种规范形排序键虽然直观但每个字符串都要 O(k log k) 排序。题目明确约束字符串只包含小写英文字母这意味着字母表总数固定为 26。既然字母表这么小我们完全可以换一个思路遍历字符串统计每个字母出现几次得到一个长度为 26 的计数数组。这个计数数组是另一种规范形。两个字符串互为异位词当且仅当它们的 26 维计数向量完全相等。eat、tea、ate 的计数向量相同都是 a:1、e:1、t:1其余字母为 0tan 和 nat 则是 a:1、n:1、t:1其余为 0。计数数组把字符顺序信息彻底丢掉只保留“每个字符的数量”恰好命中异位词的等价条件。关键收益是单个字符串的识别成本从 O(k log k) 降到 O(k)。当字符串很长、而字母表数量固定时这个优势非常明显。比如处理长度 1000 的字符串排序至少要排 1000 个字符计数却只需扫一遍然后操作 26 个槽位。下面两种语言的具体写法分别藏着一个需要解释的细节。3.2 Python用tuple、JavaScript用join(,)的细节Python 实现def group_anagrams(strs): groups defaultdict(list) for s in strs: counts [0] * 26 for ch in s: counts[ord(ch) - ord(a)] 1 key tuple(counts) groups[key].append(s) return list(groups.values())代码里对每个字符计算ord(ch) - ord(a)得到它在 0 到 25 之间的下标然后把对应计数加一。关键点是counts本身是 list在 Python 里不能作为字典键因为 list 是可变对象内部状态一变化哈希值就不稳定。所以必须转成 tupletuple 是不可变对象哈希稳定可以安全存储。tuple(counts)生成的元组里包含 26 个整数。两个元组相等的条件就是每个位置的整数都相等这正好和异位词的等价条件完全一致。本质上我们就是把一个计数向量当作哈希表键语义非常干净。JavaScript 的情况有点特殊数组本身可以直接作为对象的键但 JavaScript 在把数组转成字符串时会默认调用toString()效果等价于join(,)。看起来好像直接拿数组当 key 就行但这里有一个隐藏很深的坑function groupAnagrams(strs) { const groups new Map(); for (const s of strs) { const counts new Array(26).fill(0); for (const ch of s) { counts[ch.charCodeAt(0) - 97]; } const key counts.join(,); if (!groups.has(key)) groups.set(key, []); groups.get(key).push(s); } return [...groups.values()]; }为什么不用join()或者干脆省掉 join因为一旦某个字符出现次数达到两位数无分隔符的字符串拼接会产生歧义。举个例子字符串由 11 个 a 组成时计数数组前两个位置是 [11, 0, 0, ...]无分隔符拼接出来的开头是 1100...另一个字符串由 1 个 a 和 10 个 b 组成时计数数组前两个位置是 [1, 10, 0, ...]无分隔符拼接出来的开头同样是 1100...。两个完全不同类别的字符串居然被拼成了同一个 key。这类歧义不需要极端测试数据就能暴露。LeetCode 的用例很慷慨包含长串场景时出现两位数计数非常正常。我曾经用join()交上去几个测试用例莫名其妙失败最后逐行打印 key 才发现是这个原因。加个逗号分隔符问题立刻消失。同理如果你用字符串拼接构造 key建议用#1#0#1...这类带分隔符的格式永远别裸拼数字。3.3 两套方案横向对比给一个直观的对照表面试时可以直接照着讲对比项排序键方案计数键方案核心原理排序得到唯一字符串统计 26 个字母出现次数单字符串处理成本O(k log k)O(k)总时间复杂度O(n·k log k)O(n·k)key 的长度等于字符串长度 k固定 26小写字母场景字符集扩展性天然支持任意字符集需要扩大计数数组或改用别的结构代码可读性更好几行读完稍复杂但也不难面试推荐度先说这个清晰再提这个展示优化意识比较有意思的是空间占用。排序键方案的每个 key 长度可能达到 k如果输入里有大量长字符串且彼此不互为异位词key 的存储开销就很可观计数键方案的 key 固定是 26 个整数无论字符串多长都不变。所以从“键存储”角度讲计数键在小写字母场景下反而更省内存。复杂度上计数方案全面占优但实际运行时两者差距没有理论那么大。原因在于排序用的是 C 语言层实现常数极小而 Python 的循环逐字符统计反而要走解释器。LeetCode 这道题的数据规模是 n 最多 10⁴、字符串长度最多 100两个方案都能轻松通过。真正需要在意复杂度差别的是字符串非常长、或者输入规模变大到接近内存极限的时候。4. 从“AC完事”到“面试加分”表达顺序与追问预案4.1 拿到题先确认三件事很多同学一上来就写代码不是不行但容易漏掉关键信息。我的习惯是先确认三个问题第一字符串的取值范围。题目默认只包含小写英文字母但这必须主动跟面试官确认。如果大小写混合计数数组要扩到 52 或者 128如果有空格和数字排序键方案依然稳定计数数组就要认真考虑字典结构。确认清楚再动手能省掉后期返工。第二输入规模。n 和字符串长度的量级直接决定该选哪个方案。小规模数据两者差别不大大规模数据下计数方案更优这个判断要在代码动手前想明白。第三是否允许有重复字符串出现在同一组里。题面语义上允许但现实业务里可能有去重要求提前问一句显得你考虑问题全面。4.2 我习惯使用的解法讲解模板面试时我一般这样组织语言“我的思路是给所有异位词找一个共同标识再用哈希表按标识分组。先把每个字符串排序排序后的字符串作为这个分组的 key遍历数组把原字符串追加到对应 key 的列表中。因为互为异位词的字符串排序后完全相同它们会自然落到同一个列表里而不同类别的异位词排序结果不同所以不会互相污染。”然后补一句示例“比如 eat、tea、ate 排序后都是 aet它们就属于同一组。”接下来主动给复杂度“时间复杂度 O(n·k log k)其中 n 是字符串数量k 是最长字符串长度空间复杂度 O(n·k)。如果题目保证只含小写字母我可以进一步优化不用排序改成统计每个字符串的字符计数用 26 维计数向量做 key复杂度降到 O(n·k)。”这套表达顺序的好处是先给最简单可靠的解法让面试官确认思路正确再主动提出优化方向展示你有复杂度意识。哪怕最后代码写的是计数方案也建议先按这个顺序讲一遍逻辑链条更完整。4.3 三个大概率被追问的方向追问一如果 strs 有千万条还能这样写吗答案方向是“可以但要考虑分布式”。把 key 做一次哈希哈希结果分到不同的分区或者机器上每个分区内部继续本地分组最后把所有结果合并。这个思路和 MapReduce 的 shuffle 阶段很像。追问二如果不要求按任意顺序输出而是要按原数组第一次出现的顺序输出怎么改最简单的办法是在遍历时记录每个分组的最小下标最后对所有分组按下标排序或者用有序字典第一次遇见新 key 时记下序号。这题通常不需要这么写但面试官喜欢用这种延伸问题考察灵活度。追问三能不能用质数映射做 key可以尝试给每个字母分配一个质数字符串的 key 就是这些质数的乘积。理论上乘积相同当且仅当字母多重集相同所以也能正确分组。但实际工程中不建议字符串稍长质数乘积就可能溢出普通整数范围需要 BigInteger而且计算乘法比简单计数更昂贵。这种思路回答“哦可以但我不推荐”就足够了。如果面试官继续问“那如果有大写字母怎么办”答案也很清楚计数方案把数组从 26 扩到 128或者干脆回退到排序键方案。排序键方案对字符集没有任何假设永远是最稳的兜底。5. “先找规范形再哈希分桶”这套思路在工程里的价值5.1 数据清洗里的乱序去重做数据清洗时经常会遇到一类问题同一个实体的标识字段因为录入时顺序不一致导致查询系统把它们当成两条记录。比如公司名“华腾科技”和“科技华腾”在某些场景下可能是同一条记录的乱序输入英文名订单备注里 “AB123” 和 “B12A3” 这种字符顺序打乱的情况也偶有出现。如果业务上确认这类字符乱序应该归为同一条记录就可以用排序后的字符串作为“标准化键”做去重。不过要注意真实业务里的“乱序”多半不是纯粹的字符重排还会夹杂大小写、空格、分隔符差异。所以工程落地时通常先做归一化——统一小写、去掉空格和特殊符号——再做排序最后按排序结果分桶。这个整套流程本质上就是排序键方案在数据工程里的变形。5.2 请求参数归一与日志聚合我在做服务端日志聚合时常用到同样的思想。同一个 API 接口请求参数的顺序不同但语义完全一致如果直接把原始 URL 当维度去聚合统计就会出现大量本应合并却互相独立的数据点。把 query string 按 key 排序再把排序后的参数序列作为聚合维度就能把这类“参数乱序但实际一样”的请求归一到一个桶里。这跟字母异位词分组是不是一回事形式上不完全一样但底层思路完全一致“找到一个与排列顺序无关、只与语义内容有关的规范表示然后用这个表示做哈希分桶”。字母异位词分组训练的就是这个抽象能力刷了这道题之后再看任何“把同类东西归到一起”的需求脑子里会自然多一根弦。5.3 我对这道题的后劲体会我个人刷完这道题最大的变化不是记住了排序键而是看任何归类问题都会先问自己这类东西共同的特征是什么能不能用一个可哈希的规范形表达出来这个提问方式在写业务代码时特别有用。比如对一批商品做同款归并、对一批错误日志做聚类、对一批同义检索词做归一都需要先定义“哪些差异可以忽略”再设计一个把可忽略差异抹掉的转换函数。这道题只是把这个过程浓缩到了几十行代码里。说到这套思路的执行细节最后再分享一个小技巧如果在真实项目里遇到“需要按某种等价关系分组”的需求不要一上来就去写复杂的状态机先问能不能用单个哈希函数把等价类映射成同一个值。字母异位词的正确答案是排序函数业务里的正确答案往往也是某种简单的归一化函数。找到它代码就稳了一半。