leetcode-go/哈希/02-字母异位词分组.md

---
tags: ["LeetCode", "哈希表", "排序", "中等"]
create time: 2026-05-13 14:35
---

# 02-字母异位词分组

## 题面

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

**字母异位词**：字母相同但排列不同的字符串。

**示例 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 <= 10^4`
- `0 <= strs[i].length <= 100`
- `strs[i]` 仅包含小写字母

---

## 思路

> [!question] 💡 思考
> 两个字符串互为字母异位词，意味着它们有什么**共同特征**？能否用这个特征作为哈希表的键，把同类字符串归到一起？

### 方法一：排序作为键 ⭐（推荐入门）

核心思想：如果两个字符串是字母异位词，那么把它们各自字符**排序后得到的字符串完全一样**。

做法：遍历每个字符串，将其排序后作为哈希表的键，将原始字符串追加到对应值（切片）中。

```mermaid
flowchart LR
    A["遍历每个字符串 s"] --> B["对 s 的字符排序得到 key"]
    B --> C{"key 在哈希表中?"}
    C -->|"否"| D["新建空切片，存入 mp[key]"]
    C -->|"是"| E["取已有切片"]
    D --> F["将原始字符串 s 追加到 mp[key]"]
    E --> F
    F --> G{"还有下一个字符串?"}
    G -->|"是"| A
    G -->|"否"| H["收集所有切片的值并返回"]
```

以 `["eat", "tea", "tan", "ate", "nat", "bat"]` 为例：

| 字符串 | 排序后 key | 哈希表状态 |
|--------|-----------|-----------|
| `"eat"` | `"aet"` | `{aet: ["eat"]}` |
| `"tea"` | `"aet"` | `{aet: ["eat","tea"]}` |
| `"tan"` | `"ant"` | `{aet: [...], ant: ["tan"]}` |
| `"ate"` | `"aet"` | `{aet: ["eat","tea","ate"], ant: ["tan"]}` |
| `"nat"` | `"ant"` | `{aet: [...], ant: ["tan","nat"]}` |
| `"bat"` | `"abt"` | `{aet: [...], ant: [...], abt: ["bat"]}` |

**关键细节：**

- Go 中需要先将字符串转为 `[]rune` 或 `[]byte`，调用 `sort.Slice` 排序后再转回字符串作为 key
- 注意使用 `make(map[string][]string)` 初始化哈希表
- 最终返回值需要把 map 的所有 slice 收集到一个二维切片中

---

### 方法二：字符计数作为键 ⭐⭐（最优）

核心思想：对于只含小写字母的字符串，统计每个字符出现的次数。两个字符串的**字符计数完全相同时**，它们互为字母异位词——无需真正排序。

做法：用长度为 26 的整数数组记录 'a'~'z' 各出现几次，将其转为字符串作为哈希表键。

```mermaid
flowchart LR
    A["遍历每个字符串 s"] --> B["初始化 [26]int 计次数组"]
    B --> C["遍历 s 的每个字符 c"]
    C --> D["count[c - 'a']++"]
    D --> E{"遍历完 s?"}
    E -->|"否"| C
    E -->|"是"| F["将 count 转为字符串 key"]
    F --> G["将 s 追加到 mp[key]"]
    G --> H{"还有下一个字符串?"}
    H -->|"是"| A
    H -->|"否"| I["收集所有切片的值并返回"]
```

**为什么这个方法更快？**

- 排序法：每个字符串需 O(k log k)，k 为字符串长度
- 计次法：每个字符串只需 O(k)，k 为字符串长度
- 当字符串较长时差异显著

**两种方法对比：**

| | 时间复杂度 | 空间复杂度 | 特点 |
|--|----------|----------|------|
| 排序法 | O(n · k · log k) | O(n · k) | 直观易懂，适合面试入门 |
| 计次法 | O(n · k) | O(n · k) | 更优性能，体现对问题的深入理解 |

---

## 代码提示

### 排序法的伪代码模板

```
初始化空哈希表 mp : map[string][]string
for 每个字符串 s in strs:
    key = 对 s 的字符排序后的结果
    mp[key] = append(mp[key], s)
收集 mp 中所有 value 组成结果并返回
```

### 计次法的伪代码模板

```
初始化空哈希表 mp : map[string][]string
for 每个字符串 s in strs:
    创建长度为 26 的计次数组 cnt
    for 字符 c in s:
        cnt[c - 'a']++
    key = 将 cnt 转为唯一字符串表示
    mp[key] = append(mp[key], s)
收集 mp 中所有 value 组成结果并返回
```

---

## 技巧

> [!tip] 🔑 核心模式：等价类分组
> "找到元素的共同特征 → 作为哈希键 → 同组聚合" 是一个通用范式。本题中「排序结果」和「字符计数」都是等价的签名（signature），可用于识别一组字符串是否互为字母异位词。类似思路还出现在「有效的字母异位词」「赎金信」等问题。

> [!note] 🐹 Go 中的 HashMap 写法
> - Go 的 map 取值时 key 不存在会返回零值（`[]string` 的零值是 `nil`），直接用 `append(mp[key], s)` 是安全的——`append(nil, s)` 会得到 `[s]`
> - 利用 Go 这一特性，不需要先判断 key 是否存在再决定插入还是追加，代码更简洁

> [!info] 📊 复杂度分析（计次法）
> - 时间：O(n · k)，n 为字符串个数，k 为字符串最大长度。每个字符恰好访问一次
> - 空间：O(n · k)，哈希表存储所有字符串的副本；计次数组固定 26 个 int，忽略不计

> [!quote] 💬 面试官追问指南
> - Q: 如果字符串包含 Unicode 字符怎么办？A: 计次法需用 map[rune]int，排序法可用 `sort.Slice` 对 []rune 排序
> - Q: 能不能不用额外空间？A: 题目要求返回新结构，无法原地完成
> - Q: 字符计数如何高效转成 map 的 key？A: 用 `strconv.Itoa` 拼接或用 `bytes.Join` 构造字符串

---

## 代码

### 方法一：排序法

```go
func groupAnagrams(strs []string) [][]string {
	mp := make(map[string][]string)

	for _, s := range strs {
		// 将字符串转为 []byte 排序，得到规范化 key
		b := []byte(s)
		sort.Slice(b, func(i, j int) bool {
			return b[i] < b[j]
		})
		key := string(b)

		// Go 的 append 对 nil 切片安全，可直接追加
		mp[key] = append(mp[key], s)
	}

	// 收集结果
	result := make([][]string, 0, len(mp))
	for _, v := range mp {
		result = append(result, v)
	}

	return result
}
```

> _需导入_ `"sort"`

### 方法二：字符计数法（最优）⭐

```go
func groupAnagrams(strs []string) [][]string {
	mp := make(map[string][]string)

	for _, s := range strs {
		// 统计每个小写字母出现次数
		count := [26]int{}
		for _, c := range s {
			count[c-'a']++
		}

		// 将计次数组转为字符串作为 key，用 "#" 分隔避免歧义
		// 例如 [1,0,0,...] -> "#1#0#0#..."
		var sb strings.Builder
		sb.WriteByte('#')
		for _, v := range count {
			sb.WriteString(strconv.Itoa(v))
			sb.WriteByte('#')
		}
		key := sb.String()

		mp[key] = append(mp[key], s)
	}

	result := make([][]string, 0, len(mp))
	for _, v := range mp {
		result = append(result, v)
	}

	return result
}
```

> _需导入_ `"strconv"`, `"strings"`

> [!success] ✅ 运行验证
> LeetCode 第 49 题，通过率约 62%。计次法通常能在 5ms 内通过全部测试用例，远超排序法。掌握「等价类分组」思维后，可举一反三解决大量相似问题。