Leetcode 49: 字母异位词分组

这是一道经典的哈希表与字符串操作相关的题目，考察快速分组和使用数据结构的能力。所谓字母异位词，是指由相同的字母通过重新排列形成的不同单词。题目要求将一组字符串按照字母异位词分组。

---

问题描述

给定一个字符串数组 strs，将词组按照字母异位词进行分组，返回所有分组后的结果。字母异位词具有相同的字符，只是排列顺序不同。

输入输出示例：

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

---

适合面试的解法：排序 + 哈希表

解法描述

1. 核心思想：将异位词转化为相同的“特征 key”
   • 当两个字符串是异位词时，经过 字母排序 后，它们会转换成相同的字符串。例如：
     • "eat" 和 "tea" 排序后都变成 "aet"。
   • 我们可以用排序后的字符串作为 哈希表的 key。
2. 实现方式：
   • 对数组中的每个字符串进行排序；
   • 将排序后的字符串作为哈希表的 key；
   • 将原始字符串追加到对应的 key 所表示的列表中。
3. 为什么适合面试？
   • 逻辑清晰，不涉及复杂技巧。
   • 可以快速实现，直接解决问题。

---

代码模板

import java.util.*;class Solution {public List<List<String>> groupAnagrams(String[] strs) {// 使用一个哈希表存储分组结果Map<String, List<String>> map = new HashMap<>();// 遍历数组中的每个字符串for (String s : strs) {// 对字符串排序char[] chars = s.toCharArray();Arrays.sort(chars);String key = new String(chars);// 将排序后的字符串作为 key 插入哈希表if (!map.containsKey(key)) {map.put(key, new ArrayList<>());}map.get(key).add(s);}// 返回哈希表中所有的值return new ArrayList<>(map.values());}
}

---

复杂度分析

1. 时间复杂度：

   • 遍历所有字符串：O(N)，N 是字符串数组的长度。
   • 对每个字符串排序：O(K log K)，K 是每个字符串的平均长度。
   • 总复杂度：O(N * K log K)。

2. 空间复杂度：

   • 哈希表存储所有字符串，每个字符串最多需要存储一次，因此是 O(N * K)。

---

适用场景

• 面试推荐解法： 逻辑简单清晰，容易快速实现。
• 基于排序的方式适合用来处理字母异位词，无法修改原始字符串的情况下效果较好。

---

解法 2：计数特征 + 哈希表

解法描述

1. 核心思想：用字符计数数组代替排序
   • 对于异位词，其字符的频率分布是相同的。例如：
     • "eat" 和 "tea" 的字母分布均为 {e:1, a:1, t:1}。
   • 可以用一个固定大小为 26 的数组（代表英文字母）来统计每个字母的频率。
   • 将频率数组转换为字符串作为哈希表的 key。
2. 实现方式：
   • 遍历每个字符串，统计其字符频率。
   • 构造哈希表，以字符频率数组的字符串表示作为 key。
   • 将具有相同字符频率的字符串分组。
3. 优化点：
   • 避免了排序操作，相当于将 O(K log K) 降低到 O(K)。

---

代码模板

import java.util.*;class Solution {public List<List<String>> groupAnagrams(String[] strs) {// 使用一个哈希表存储分组结果Map<String, List<String>> map = new HashMap<>();// 遍历数组中的每个字符串for (String s : strs) {// 统计字符频率int[] count = new int[26];for (char c : s.toCharArray()) {count[c - 'a']++;}// 将频率数组转化为字符串作为 keyStringBuilder keyBuilder = new StringBuilder();for (int i = 0; i < 26; i++) {keyBuilder.append(count[i]).append(",");}String key = keyBuilder.toString();// 将字符串插入哈希表if (!map.containsKey(key)) {map.put(key, new ArrayList<>());}map.get(key).add(s);}// 返回哈希表中所有的值return new ArrayList<>(map.values());}
}

---

复杂度分析

1. 时间复杂度：

   • 遍历所有字符串：O(N)，N 是数组长度。
   • 统计字符频率：O(K)，K 是字符串平均长度。
   • 总复杂度：O(N * K)。

2. 空间复杂度：

   • 哈希表存储结果，空间复杂度为 O(N * K)。

---

适用场景

• 当字符串较长时，字母计数的效率更高，可以替代排序操作。
• 非常适合后期优化和性能要求较高的场景。

---

解法 3：质数乘积映射（进阶解法）

解法描述

1. 核心思想：将字符映射为质数，用乘积唯一标记异位词
   • 因为不同质数的乘积是唯一的（数学性质），我们可以用每个字母对应一个质数，将一个字符串的乘积表示为一个数值。
   • 如果两个字符串组成的质数乘积相同，则它们必然是字母异位词。
2. 实现方式：
   • 定义一个数组，将每个字母从 'a' 到 'z' 映射到第 i 个质数。
   • 对每个字符串计算其映射值（用长整型避免溢出），用其作为哈希表的 key 进行分组。

---

代码模板

import java.util.*;class Solution {public List<List<String>> groupAnagrams(String[] strs) {// 每个字母对应的质数值int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};Map<Long, List<String>> map = new HashMap<>();for (String s : strs) {long key = 1;for (char c : s.toCharArray()) {key *= primes[c - 'a'];}if (!map.containsKey(key)) {map.put(key, new ArrayList<>());}map.get(key).add(s);}return new ArrayList<>(map.values());}
}

---

复杂度分析

1. 时间复杂度：

   • 遍历每个字符串：O(N)。
   • 计算质数乘积：O(K)。
   • 总复杂度：O(N * K)。

2. 空间复杂度：

   • 哈希表存储结果，复杂度为 O(N * K)。

---

适用场景

• 非常高效的解法，但只有在需要性能极致优化时才选择。
• 不太适合面试，数学背景不足时可能导致解法难以理解。

---

快速AC策略总结

1. 推荐：排序 + 哈希表（解法 1）

   • 最适合面试，逻辑清晰：
     • 用排序生成唯一键。
     • 易实现，时间、空间效率均合理。

2. 优化：计数特征 + 哈希表（解法 2）

   • 如果字符串较长或对性能有更高要求：字母计数比排序更高效。

3. 进阶：质数乘积（解法 3）

   • 如果需要进一步优化或展示数学思维的独特解法，可以考虑此法，但面试中不便于解释基础。

熟练掌握解法 1 和解法 2，可以在面试中快速 AC 并展现对字符串操作和哈希表应用的理解能力！