MUYI · 后端工程师的生产级知识体系

Appearance

字母异位词分组 ​

一、题目（LeetCode 49 · 中等 · Hot100） ​

给定一个字符串数组 strs，将字母异位词组合在一起（异位词：字母相同、顺序可以不同）。返回分组后的列表，分组顺序与组内顺序均任意。

输入：strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出：[["bat"],["nat","tan"],["ate","eat","tea"]]

二、思路演进 ​

2.1 暴力：两两判等归并 ​

对每两个串各自排序后比较，把等价的串并进同一组。O(n²) 次比较，每次 O(k log k)，n 一大立刻不可用。更本质的问题和 两数之和 一样：两两关系没有落在一个可以直接当 key 用的形态上。

2.2 关键洞察：为异位词设计"规范形"（canonical key） ​

互为异位词的串无论顺序怎么打乱，有两个不变量：

  • 排序后完全一致——"eat" 和 "tea" 排完都是 aet；
  • 字母计数完全一致——都是 a:1、e:1、t:1。

把任一不变量序列化成字符串，就能当 HashMap 的 key：同组词算出的 key 天然相同，一次遍历对号入座。思维上仍是"把 O(n²) 的两两比较压成 O(n) 的逐个入桶"。

两种 key 的代价差别：

key 形态单个串编码代价总时间
排序串 aetO(k log k)O(n · k log k)
计数串 1#0#…#1O(k + 26)O(n · k)

k 大时计数法更优；本题 k ≤ 100，两者都能过。

三、复杂度分析 ​

以计数法为主代码，n 个串、平均长度 k：

  • 时间 O(n · k)：每个串扫一遍统计 26 个计数 O(k)，再拼一段固定长度 26 的 key（常数）。排序法则是 O(n · k log k)。
  • 空间 O(n · k)：所有 key 与分组本身；计数数组 O(26) 是常数级临时空间。

四、代码 ​

java
package org.example;

import java.util.*;

/**
 * @author MUYI
 * @version 1.0
 * @date 2026/10/17
 */
public class LeetCode_49 {

    public static void main(String[] args) {
        List<List<String>> groups = groupAnagrams(
                new String[]{"eat", "tea", "tan", "ate", "nat", "bat"});
        groups.forEach(System.out::println);    // 期望按组分出 bat / nat,tan / eat 组
    }

    public static List<List<String>> groupAnagrams(String[] strs) {
        // key = 26 个计数的定界拼接，value = 同组单词
        Map<String, List<String>> groups = new HashMap<>();
        for (String s : strs) {
            int[] count = new int[26];
            for (char c : s.toCharArray()) {
                count[c - 'a']++;
            }
            // int[] 不能直接当 key（按引用判等），必须序列化
            StringBuilder key = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                key.append(count[i]).append('#');   // '#' 定界，防 "1,11" 与 "11,1" 撞 key
            }
            groups.computeIfAbsent(key.toString(), k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(groups.values());
    }

    /** 排序 key 版：更短，k 小时足够用 */
    public static List<List<String>> groupBySort(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String s : strs) {
            char[] arr = s.toCharArray();
            Arrays.sort(arr);
            groups.computeIfAbsent(new String(arr), k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(groups.values());
    }

}

五、坑点 ​

  • int[26] 直接做 key 必错：数组没有重写 hashCode/equals，HashMap 按"引用相等"判等，每组都会裂成一格。必须转 String（Arrays.toString(count) 或手动拼接均可）。
  • 计数拼接必须定界："1"+"11" 和 "11"+"1" 不定界会拼出同一个 key，用 # 之类的分隔符隔开每个计数。
  • 排序版别用 arr.toString()：char[] 的 toString 是 [C@hash，要 new String(arr)。
  • computeIfAbsent 比手写 containsKey + get + put 简洁，且只查一次表。
  • 空串是合法组员——空串之间互为异位词，上述逻辑无需特判。

六、变形追问 ​

  • 变体一（字符集扩大）：若字符不止小写字母（大写、Unicode），计数法要扩到整个字符集就不划算。退回排序 key——O(k log k) 但与字符集大小无关。
  • 变体二（key 还能再省吗）：面试官常追问计数法的优化。若保证各字母出现次数 < 8，可用一个 long 按 3 bit 一段打包计数。这样把 26 段字符串压成一个整数，哈希计算也随之变快。找到字符串中所有字母异位词 则是同一计数思想在滑窗里的应用。

2026-10 新增（E 轨 · Hot100 第一批）。