243 lines
7.2 KiB
Markdown
243 lines
7.2 KiB
Markdown
---
|
||
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 内通过全部测试用例，远超排序法。掌握「等价类分组」思维后，可举一反三解决大量相似问题。
|