LeetCode Hot 100：49. 字母异位词分组

题目

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

示例 1:‌

输入:‌ strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出:‌ [["bat"],["nat","tan"],["ate","eat","tea"]]

解释：‌

• 在 strs 中没有字符串可以通过重新排列来形成 "bat"。
• 字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。
• 字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。

示例 2:‌

输入:‌ strs = [""]

输出:‌ [[""]]

示例 3:‌

输入:‌ strs = ["a"]

输出:‌ [["a"]]

提示：‌

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

题解

这道题的难点在于如何为每个单词进行词内排序。

import "slices"

func groupAnagrams(strs []string) [][]string {
    hashTable := make(map[string][]string, len(strs))
    for _, s := range strs {
        b := []byte(s)
        slices.Sort(b)
        key := string(b)
        hashTable[key] = append(hashTable[key], s)
    }
    answer := make([][]string, 0, len(hashTable))
    for _, value := range hashTable {
        answer = append(answer, value)
    }
    return answer
}

这里用到了 Go 的slices包，它是用来处理切片的。所以针对一个仅包含字母的字符串s，我们将其转换为[]byte字节切片后处理。

slices.Sort()是原地排序，没有返回值。只能在下一行拿到已经排好序的值并将其转为字符串。

Go 的map只能接受值类型（也就是可以通过==进行比较的那些），所以没有map[[]byte][]string这种玩意。

这句是精华：hashTable[key] = append(hashTable[key], s)，它意味着：把hashTable上key键所对应的值（数组）追加上s。它厉害在，如果此时hashTable里没有存key键，它起到的就是"在hashTable里key键对应的值里存入一个包含s的数组"的作用。append()作为 Go 的全局方法还是太权威了。

最幽默的是为hashTable加上一个len(strs)的初始化容量尝试优化之后，执行用时反而长了 1ms，但内存占用确实大幅下降了。说明 LeetCode 提供的测试数据其实大多都不是最坏情况。

下面是 Java 做法：

import java.util.Arrays;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> hashTable = new HashMap<>();
        for (String str : strs) {
            char[] c = str.toCharArray();
            Arrays.sort(c);
            String s = new String(c);
            List<String> list = hashTable.get(s);
            if (list == null) {
                list = new ArrayList<>();
                hashTable.put(s, list);
            }
            list.add(str);
        }
        return new ArrayList<>(hashTable.values());
    }
}

这里用到了 Java 的java.util.Arrays包，它是用来处理数组的。我们将str转换为char[]数组后处理。

Java 的Arrays.sort()也是原地排序，没有返回值。

下面是重点：

Java 里"一切皆对象，皆为引用"。在一个周期里（我们假设当hashTable为空），我们通过List<String>声明了list的类型；尝试把hashTable.get(key)的返回值赋给它（尝试让list引用的对象变成hashTable.get(key)返回的对象）‌会理所当然地失败（因为hashTable此时并不包含key这个键，所以查找不到键所对应的值对象），所以list的值是未初始化的null；然后我们初始化了它（把它指向一个new ArrayList<>()返回的空列表）；接着把这个空列表list作为值对象塞进了map里，它对应的键是对此轮循环从strs里遍历到的单词str进行重排和转换后得到的s。

有意思的来了，我们只需要在确保hashTable里确实有了list对象之后，对list进行追加（也就是，调用list.add(str)）。此时hashTable内部的内容也会同步更新，因为事实上我们操作的是同一个名为list的对象。

这对于直接从 Java 开始入坑程序设计的同学们来说应该是理所应当的事情。然而，Go 中的传递是非常直白的值拷贝，而 Java 拷贝的是隐藏指针。

• 本质相同‌：无论是 Java 还是 Go，在计算机底层都遵循 ‌"万物皆是值传递"‌‌。函数传参时，永远是在内存里复制（Copy）了一份数据投递过去。
• 表现不同‌：
  • Go 语言表现得更直白‌：它把"指针"和"普通值"在语法上清晰地分开了（有 *int 和 int 的区别）。需要改外部就传指针，不需要就传值。
  • Java 语言套了一层语法糖‌：Java 为了隐藏指针的复杂性，把除基本类型外的一切对象都强制设计成了"隐式指针（引用）"。它传递的是指针地址的拷贝‌，所以它能在函数内部直接整容（修改对象属性），但无法直接换头（把对象重新赋值）。

但其实这道题还有一个解法。

func groupAnagrams(strs []string) [][]string {
    // Key 是一个长度为 26 的 byte 数组，代表 a-z 出现的次数
    hashTable := make(map[[26]byte][]string)

    for _, s := range strs {
        var count [26]byte // 每次循环初始化一个全 0 数组
        
        // 统计每个字母出现的频次
        for i := 0; i < len(s); i++ {
            count[s[i]-'a']++
        }
        
        // [26]byte 是可比较类型，直接作为 Key 写入，免去了排序和转字符串的开销！
        hashTable[count] = append(hashTable[count], s)
    }

    // 同样使用预分配容量收集结果
    result := make([][]string, 0, len(hashTable))
    for _, val := range hashTable {
        result = append(result, val)
    }
    return result
}

字母异位词分组的究极优化：计数法（26位数组）‌

"排序法"的时间复杂度是O(N*K*logK)，其中N是单词数，K是单词最大长度。如果单词很长，排序会变慢。

因为题目限定了只包含小写字母，我们可以用 26位数组计数法‌，把时间复杂度降到纯线性的O(N*K)。

在 Go 中，‌固定大小的数组（Array）是可以直接作为 Map 的 Key 的‌（因为数组长度固定，可以相互比较，而切片 Slice 不行）。

为什么这个做法在 Go 里很无敌？‌
我们不需要像排序法那样做 []byte 到 string 的强制类型转换，也没有调用任何排序函数。全量操作都在栈上完成，速度极快。

记录

1. Java 和 Go 在值传递方面有明显的不同，这点需要特别注意。

2. Go 的引用类型在make时可以指定容量。make的第一个参数永远是类型。

   • 对于切片，有三个参数：第二个参数是长度（即已经占用的多少，一般初始化是都填0确保全空），第三个参数是容量（触发扩容之前，切片最多可以存多少）。
   • 对于map，第二个参数是容量。

3. Java 也有很方便的for写法，for (String str : strs) {表示遍历strs中的所有String类型对象，并将每一次取到的值赋为str。Go 里类似的写法是for _, s := range strs {，表示遍历strs里的所有对象，并将每一次取到的值赋为s，_表示我们不在意循环次数（当前索引元素的下标），如果在意可以换成i之类的变量名（从0开始：它数值上等于循环次数 - 1）。

4. Java 的HashMap是一个功能丰富的对象，自带大量内置方法，所以可以用map.set(key)进行增改，map.values()一键遍历；但是 Go 的map是一个极简的原生类型，没有任何内置方法，所以要用map[key] = value的方式来增改，用for range循环来遍历。‌Go 里的map和 Java 的HashMap一样，都是无序的。‌

5. Java 的map.values()返回的是Collection<List<String>>。

   Gemini 老师如是说：

   在 Java 的集合框架里，Collection 是 List 的亲爸爸（父接口）‌‌。

   Java 有一个铁律：‌儿子可以自动冒充爸爸，但爸爸绝对不能直接变成儿子。‌

   所以，虽然 Collection 里面确实装着一堆列表，但它缺少了 List 接口特有的很多方法（比如不能通过下标 get(i) 随机访问）。Java 编译器一看："你给我一个残疾的 Collection 爸爸，怎么能满足 LeetCode 要的 List 儿子呢？" 于是直接编译报错。

   为什么非要套一层 new ArrayList<>(...)‌？‌

   这就好比你手里有一袋刚从地里摘下来的散装土豆（Collection），但客户（LeetCode）要求必须用指定的长方形塑料标准箱（ArrayList）来装。

   你必须执行 new ArrayList<>(...)，它的底层逻辑是：

   1. 真正地在堆内存里开辟一块连续的、标准的 ArrayList 空间。
   2. 把 hashTable.values() 里面的那堆数据，‌一个一个排好队拷贝塞进这个新箱子里。
   3. 拿着这个标准箱去交差。

   ……狗屎。

   对比一下，你就会发现 Go 语言的设计有多么实用主义：

   在 Go 语言里，你要返回 [][]string，你遍历 hashTable 得到的 value 本身就是 []string，你用 append 攒出来的 answer 本身就是 [][]string。类型天生完美契合，没有任何所谓的"接口转换障碍"，直接 return answer 干净利落。

6. List<String> list这一块本身有意义吗？我是否应该将其理解为它界定了list这个引用的类型？还有我想知道，为什么一个简单的变量list会跑到堆上？不应该在栈上吗？

   问题一：‌List<String> list 这一块本身有意义吗？‌

   非常有意义。你的理解完全正确：它界定了变量的类型，并具有两个核心作用。‌

   1. 它是给编译器看的"契约"：

      在 Java 这种强类型语言中，编译器必须提前知道 list 这个变量（遥控器）‌能用来干什么‌。

      通过写 List<String> list，你告诉了 Java 编译器："听着，我这个变量以后只能用来遥控 List（列表）类型的对象，而且里面装的只能是 String（字符串）。"

   2. 安全防火墙：

      一旦界定了类型，如果你后面不小心写了 list = new HashMap(); 或者 list.add(123);（塞入数字），编译器在编译阶段就会直接报错拦截，绝对不让有bug的代码跑到生产环境。

   (注：Java 10 以后也支持写 *var list = map.get(key);* 让编译器自己去猜类型，但它底层的强类型本质依然没变。)

   问题二：为什么一个简单的变量 list 会跑到堆上？不应该在栈上吗？‌

   真相是：变量 list 本身在【栈】上，但它指向的庞大肉身在【堆】上。‌

   你没有记错，局部变量确实应该在栈（Stack）‌里。计算机科学为了兼顾速度和灵活性，把内存分成了两个世界：

   1. 栈（Stack）：存放轻量级的"遥控器"‌

   当你在方法里写 List<String> list 时，JVM 确实在栈内存里开辟了一小块空间，放了这个名叫 list 的变量。

   但是，栈的特点是"快"和"规整"，它要求存在里面的东西必须大小固定、用完即毁。一个可能装 100 个单词也可能装 10000 个单词的列表，栈是根本放不下的。

   所以，栈里的 list 变量极其小，‌它里面存的仅仅是一个 4 字节或 8 字节的"内存地址"‌‌（也就是指针/遥控器）。

   2. 堆（Heap）：存放重量级的"真实肉身"‌

   当你执行 new ArrayList<>() 时，Java 才会真正跑到堆（Heap）内存里，开辟一大块地方来准备存放一堆字符串。

   堆的特点是"大"和"自由"。

   💡 连线：‌

   最终的画面是：

   • 你的局部变量 list 老老实实地呆在栈里，它手里攥着一个地址（比如 0x7fff）。

   • 而真正的 ArrayList 庞大对象躺在堆里的 0x7fff 编号的温床上。

   • 当你执行 list.add(s) 时，CPU 是先去栈里看 list 的值是 0x7fff，然后顺藤摸瓜，通过网络（总线）跑到堆里的 0x7fff 地方，把数据塞进去。

   😴 终极大总结

   因为 list 变量本身（那个地址）在栈上，所以当这个循环或者方法结束时，栈里的 list 变量会瞬间被销毁‌。

   但是！因为你在中途执行了 map.put(key, list)，也就是把堆里的那个 0x7fff 的地址也抄了一份交给了 map。所以，虽然你栈里的 list 没了，但堆里的那个列表肉身依然活着‌，因为 map 还牵着它呢！

   这就是为什么 map 最终能成功把数据返回给 LeetCode 的原因。

……怎么 Gemini 老师也会说病句啊？