Leetcode49:字母异位词分组

电脑硬件
2025-09-14 08:33:01

Leetcode 49: 字母异位词分组

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

问题描述

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

输入输出示例：

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

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

代码模板 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()); } }

复杂度分析

时间复杂度：

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

空间复杂度：

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

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

解法 2：计数特征 + 哈希表解法描述核心思想：用字符计数数组代替排序对于异位词，其字符的频率分布是相同的。例如： "eat" 和 "tea" 的字母分布均为 {e:1, a:1, t:1}。可以用一个固定大小为 26 的数组（代表英文字母）来统计每个字母的频率。将频率数组转换为字符串作为哈希表的 key。实现方式：遍历每个字符串，统计其字符频率。构造哈希表，以字符频率数组的字符串表示作为 key。将具有相同字符频率的字符串分组。优化点：避免了排序操作，相当于将 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']++; } // 将频率数组转化为字符串作为 key StringBuilder 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()); } }

复杂度分析

时间复杂度：

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

空间复杂度：

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

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

解法 3：质数乘积映射（进阶解法）解法描述核心思想：将字符映射为质数，用乘积唯一标记异位词因为不同质数的乘积是唯一的（数学性质），我们可以用每个字母对应一个质数，将一个字符串的乘积表示为一个数值。如果两个字符串组成的质数乘积相同，则它们必然是字母异位词。实现方式：定义一个数组，将每个字母从 '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()); } }

复杂度分析

时间复杂度：

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

空间复杂度：

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

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

快速AC策略总结

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

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

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

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

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