LeetCode LCR 033. 字母异位词分组

LeetCode LCR 033. 字母异位词分组

---

题目描述

给定一个字符串数组 strs，要求将互为变位词（字符出现次数相同但顺序不同的字符串）的字符串分组，并返回分组后的结果列表。
示例：
输入：strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出：[["bat"], ["nat","tan"], ["ate","eat","tea"]]

---

核心思路

变位词的核心特征是字符组成完全相同，只是顺序不同。因此，可以通过以下步骤实现分组：

1. 统一标识：将每个字符串转换为统一的“标识”，使得同一组的变位词具有相同的标识。
2. 哈希表映射：用哈希表存储“标识”到“字符串列表”的映射，最终提取所有值即为结果。

---

解法实现

方法：排序 + 哈希表

1. 排序生成标识：将每个字符串的字符排序，排序后的字符串作为哈希表的键。
2. 哈希表分组：遍历所有字符串，以排序后的字符串为键，将原始字符串存入对应的列表中。

时间复杂度：

• 每个字符串排序的时间复杂度为 O(k log k)（k 为字符串长度）。
• 总体时间复杂度：O(n * k log k)，其中 n 是字符串数量。

空间复杂度：

• O(n * k)，用于存储哈希表的所有键和值。

public static List<List<String>> groupAnagrams(String[] strs) {HashMap<String, List<String>> map = new HashMap<>();for (String str : strs) {char[] array = str.toCharArray();Arrays.sort(array); // 生成统一标识String key = new String(array);List<String> list = map.getOrDefault(key, new ArrayList<>());list.add(str);map.put(key, list); // 更新哈希表}return new ArrayList<>(map.values());
}

---

代码解析

1. 排序生成键：

   char[] array = str.toCharArray();
   Arrays.sort(array);
   String key = new String(array);
   

   • 将字符串转为字符数组并排序，排序后的字符串作为唯一标识。
   • 例如，"eat" 和 "tea" 排序后均为 "aet"，因此归为同一组。

2. 哈希表操作：

   List<String> list = map.getOrDefault(key, new ArrayList<>());
   list.add(str);
   map.put(key, list);
   

   • map.getOrDefault：安全获取键对应的列表，若不存在则新建空列表。
   • 将当前字符串加入列表，并更新哈希表。

3. 返回结果：

   return new ArrayList<>(map.values());
   

   • 直接提取哈希表的所有值（即分组后的列表）。

---

示例解析

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

1. 排序生成键：
   • "eat" → "aet"，"tea" → "aet"，"ate" → "aet"
   • "tan" → "ant"，"nat" → "ant"
   • "bat" → "abt"
2. 哈希表分组：
   • "aet" → ["eat", "tea", "ate"]
   • "ant" → ["tan", "nat"]
   • "abt" → ["bat"]

---

优化与变体

1. 字符计数法：
   用字符出现次数作为标识（例如 a1b0c2...），避免排序的时间开销。
   时间复杂度：O(n * k)（k 为字符集大小）。
   适用场景：字符串较长时更高效。

   public static 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']++;String key = Arrays.toString(count); // 例如 "[2,0,1,...]"map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);}return new ArrayList<>(map.values());
   }
   

2. 质数乘积法：
   为每个字母分配一个质数，计算字符串的质数乘积作为键。
   优点：避免字符串拼接或排序的开销。
   缺点：可能溢出（需使用大整数）。

---

力扣通过截图

总结

方法	时间复杂度	空间复杂度	适用场景
排序+哈希表	O(n * k log k)	O(n * k)	通用场景，代码简洁
字符计数法	O(n * k)	O(n * k)	字符串较长时更优
质数乘积法	O(n * k)	O(n)	小规模数据，无溢出风险时使用

推荐使用排序+哈希表法，代码简洁且易于理解，适合面试快速实现。若追求极致性能，可尝试字符计数法。