一、题目原题重现字母异位词分组是LeetCode哈希表应用的经典高频题也是程序员面试必考算法题型核心考察哈希表键值设计、字符串特征提取、分组逻辑实现难度适中非常适合巩固哈希表实战用法夯实算法基础。1.1 题目原文给你一个字符串数组strs请你将字母异位词组合在一起可以按任意顺序返回结果列表。字母异位词定义由重新排列源单词的字母得到的新单词且所有字母的出现次数完全相同例如 “eat” 和 “tea” 互为字母异位词两个单词可通过重排互相得到。1.2 题目约束数组长度范围1 strs.length 10⁴单个字符串长度0 strs[i].length 100字符串仅包含小写英文字母1.3 示例演示示例演示示例 1 输入: strs [eat, tea, tan, ate, nat, bat] 输出: [[bat],[nat,tan],[ate,eat,tea]] 示例 2 输入: strs [] 输出: [[]] 示例 3 输入: strs [a] 输出: [[a]]二、解题思路全解析2.1 核心问题拆解解决字母异位词分组的核心关键找到字母异位词的统一唯一特征标识让同一组异位词拥有相同标识不同组标识完全区分再借助哈希表完成分组这也是同类分组题型的通用解题逻辑。基于该核心本题有两种主流解法分别适配入门理解和最优答题场景。2.2 解法一排序法直观基础解法核心思路互为字母异位词的字符串排序后得到的结果完全一致例如 “eat” 和 “tea” 排序后均为 “aet”利用这一特性将排序后的字符串作为哈希表唯一键实现分组存储。初始化Python字典作为哈希表键为排序后的字符串值为对应字母异位词列表遍历数组内每个字符串对字符串排序并拼接生成特征键将原字符串追加到哈希表对应键的列表中键不存在则初始化空列表遍历完成后将哈希表的值转为列表即为最终分组结果代码实现Python解法一排序法代码from typing import List class Solution: def groupAnagrams(self, strs: List[str]) - List[List[str]]: # 哈希表key排序后字符串value对应字母异位词列表 anagram_map {} for s in strs: # sorted返回字符列表列表不可哈希需用join拼接为字符串作为键 key .join(sorted(s)) # 键不存在则初始化空列表存在则直接追加当前字符串 if key not in anagram_map: anagram_map[key] [] anagram_map[key].append(s) # 字典values为视图对象强转列表后符合题目二维列表输出格式 return list(anagram_map.values()) # 本地测试验证 if __name__ __main__: sol Solution() print(sol.groupAnagrams([eat, tea, tan, ate, nat, bat])) print(sol.groupAnagrams([])) print(sol.groupAnagrams([a]))复杂度分析时间复杂度O ( n k log k ) O(nk\log k)O(nklogk)其中n nn为字符串数组长度k kk为单个字符串的最大长度对每个字符串执行排序的耗时为O ( k log k ) O(k\log k)O(klogk)共遍历n nn个字符串空间复杂度O ( n k ) O(nk)O(nk)额外空间主要用于哈希表存储所有字符串字符不计返回结果本身的空间开销属于必要空间消耗优缺点✅ 优点思路直观易懂代码极简无复杂逻辑新手极易上手适合理解核心分组逻辑❌ 缺点排序操作有额外耗时处理超长字符串时效率偏低2.3 解法二字符计数法最优解面试首选核心思路字母异位词的每个字符出现次数完全相同利用这一本质特征统计26个小写字母的出现次数生成计数特征作为哈希表键跳过排序步骤时间复杂度优化至线性级别是本题最优解法。每个字符串对应初始化长度为26的计数列表对应a-z初始值全0索引从0开始依次对应a到z遍历字符串字符通过ord()计算字符对应索引统计每个字母出现次数Python中列表不可哈希无法直接作为字典键需转换为元组作为哈希表唯一特征键按键分组存储最后将哈希表值转为列表返回代码实现Python解法二字符计数法最优解from typing import List class Solution: def groupAnagrams(self, strs: List[str]) - List[List[str]]: # 哈希表key字符计数元组value字母异位词列表 anagram_map {} for s in strs: # 初始化26位字母计数数组索引0~25分别对应小写字母a~z count [0] * 26 # 遍历字符统计每个字母出现次数 for char in s: # 计算字符对应索引从0开始计数保证小写字母映射无偏差 idx ord(char) - ord(a) count[idx] 1 # 列表不可哈希转为元组后作为字典键 key tuple(count) # 键不存在则初始化存在则追加 if key not in anagram_map: anagram_map[key] [] anagram_map[key].append(s) return list(anagram_map.values()) # 进阶简化写法可选用defaultdict省去判空逻辑 # from collections import defaultdict # class Solution: # def groupAnagrams(self, strs: List[str]) - List[List[str]]: # anagram_map defaultdict(list) # for s in strs: # count [0]*26 # for c in s: # count[ord(c)-ord(a)] 1 # anagram_map[tuple(count)].append(s) # return list(anagram_map.values()) # 本地测试 if __name__ __main__: sol Solution() print(sol.groupAnagrams([eat, tea, tan, ate, nat, bat]))执行过程演示以 “eat” 为例索引从0开始计数初始化计数列表[0,0,0,...,0]共26个0对应a-z字符 ‘e’ 对应索引ord(e)-ord(a)4→count[4] 1→[0,0,0,0,1,0,...0]字符 ‘a’ 对应索引ord(a)-ord(a)0→count[0] 1→[1,0,0,0,1,0,...0]字符 ‘t’ 对应索引ord(t)-ord(a)19→count[19] 1→[1,0,0,0,1,0,...,1,...0]转换为元组作为键“tea” 和 “ate” 会生成完全相同的键自动归为一组复杂度分析时间复杂度O ( n k ) O(nk)O(nk)仅需线性遍历数组所有字符无排序等高耗时操作遍历效率拉满空间复杂度O ( n k ) O(nk)O(nk)额外开销来自哈希表存储和固定大小的计数数组不计返回结果空间消耗合理优缺点✅ 优点时间最优无排序开销全场景适配稳定性极强✅ 优点特征键唯一性拉满完全规避排序潜在问题面试首选❌ 缺点代码逻辑稍复杂需理解字符编码与计数转换逻辑三、核心注意事项与易错点空字符串处理空字符串无字符计数列表全0排序后为空串可正常单独分组无需额外判断哈希键类型禁忌Python列表不可作为字典键计数列表必须转元组排序后字符列表必须用join拼接为字符串否则代码直接报错字符索引计算通过ord(char)-ord(a)映射0-25索引严格对应小写字母无索引越界风险返回格式规范字典values()为视图对象必须用list()强转才能得到题目要求的二维列表格式四、两种解法性能对比解法类型时间复杂度空间复杂度适用场景推荐指数排序法O ( n k log k ) O(nk\log k)O(nklogk)O ( n k ) O(nk)O(nk)字符串较短、追求代码简洁、快速入门⭐⭐⭐⭐字符计数法O ( n k ) O(nk)O(nk)O ( n k ) O(nk)O(nk)全场景、面试答题、大规模数据处理⭐⭐⭐⭐⭐五、全文总结与思考延伸5.1 全文总结本题核心考点哈希表键值设计、字符串特征提取、分组算法实现是哈希表实战的经典入门题型排序法适合入门理解代码简洁但时间复杂度偏高适合小规模数据场景字符计数法是本题最优解通过空间换时间时间复杂度优化至O(nk)面试务必优先使用同类分组题型均可借鉴该思路提取统一特征作为键借助哈希表实现高效分组通用性极强。5.2 思考延伸通用场景适配若字符串包含Unicode字符而非仅小写字母排序法仍通用直接按字符排序计数法可改用collections.Counter统计字符频次再转为元组作为键。代码进阶写法Python中可使用defaultdict(list)省去键不存在的判空逻辑简化代码适合熟练后使用基础学习阶段保留显式判断更易理解。刷题延伸吃透本题后可练习 LeetCode 242.有效的字母异位词基础前置题、LeetCode 438.找到字符串中所有字母异位词进阶题巩固字符计数与哈希表用法。
LeetCode 49. 字母异位词分组 超详细题解（Python版）｜排序法+字符计数法双解法
一、题目原题重现字母异位词分组是LeetCode哈希表应用的经典高频题也是程序员面试必考算法题型核心考察哈希表键值设计、字符串特征提取、分组逻辑实现难度适中非常适合巩固哈希表实战用法夯实算法基础。1.1 题目原文给你一个字符串数组strs请你将字母异位词组合在一起可以按任意顺序返回结果列表。字母异位词定义由重新排列源单词的字母得到的新单词且所有字母的出现次数完全相同例如 “eat” 和 “tea” 互为字母异位词两个单词可通过重排互相得到。1.2 题目约束数组长度范围1 strs.length 10⁴单个字符串长度0 strs[i].length 100字符串仅包含小写英文字母1.3 示例演示示例演示示例 1 输入: strs [eat, tea, tan, ate, nat, bat] 输出: [[bat],[nat,tan],[ate,eat,tea]] 示例 2 输入: strs [] 输出: [[]] 示例 3 输入: strs [a] 输出: [[a]]二、解题思路全解析2.1 核心问题拆解解决字母异位词分组的核心关键找到字母异位词的统一唯一特征标识让同一组异位词拥有相同标识不同组标识完全区分再借助哈希表完成分组这也是同类分组题型的通用解题逻辑。基于该核心本题有两种主流解法分别适配入门理解和最优答题场景。2.2 解法一排序法直观基础解法核心思路互为字母异位词的字符串排序后得到的结果完全一致例如 “eat” 和 “tea” 排序后均为 “aet”利用这一特性将排序后的字符串作为哈希表唯一键实现分组存储。初始化Python字典作为哈希表键为排序后的字符串值为对应字母异位词列表遍历数组内每个字符串对字符串排序并拼接生成特征键将原字符串追加到哈希表对应键的列表中键不存在则初始化空列表遍历完成后将哈希表的值转为列表即为最终分组结果代码实现Python解法一排序法代码from typing import List class Solution: def groupAnagrams(self, strs: List[str]) - List[List[str]]: # 哈希表key排序后字符串value对应字母异位词列表 anagram_map {} for s in strs: # sorted返回字符列表列表不可哈希需用join拼接为字符串作为键 key .join(sorted(s)) # 键不存在则初始化空列表存在则直接追加当前字符串 if key not in anagram_map: anagram_map[key] [] anagram_map[key].append(s) # 字典values为视图对象强转列表后符合题目二维列表输出格式 return list(anagram_map.values()) # 本地测试验证 if __name__ __main__: sol Solution() print(sol.groupAnagrams([eat, tea, tan, ate, nat, bat])) print(sol.groupAnagrams([])) print(sol.groupAnagrams([a]))复杂度分析时间复杂度O ( n k log k ) O(nk\log k)O(nklogk)其中n nn为字符串数组长度k kk为单个字符串的最大长度对每个字符串执行排序的耗时为O ( k log k ) O(k\log k)O(klogk)共遍历n nn个字符串空间复杂度O ( n k ) O(nk)O(nk)额外空间主要用于哈希表存储所有字符串字符不计返回结果本身的空间开销属于必要空间消耗优缺点✅ 优点思路直观易懂代码极简无复杂逻辑新手极易上手适合理解核心分组逻辑❌ 缺点排序操作有额外耗时处理超长字符串时效率偏低2.3 解法二字符计数法最优解面试首选核心思路字母异位词的每个字符出现次数完全相同利用这一本质特征统计26个小写字母的出现次数生成计数特征作为哈希表键跳过排序步骤时间复杂度优化至线性级别是本题最优解法。每个字符串对应初始化长度为26的计数列表对应a-z初始值全0索引从0开始依次对应a到z遍历字符串字符通过ord()计算字符对应索引统计每个字母出现次数Python中列表不可哈希无法直接作为字典键需转换为元组作为哈希表唯一特征键按键分组存储最后将哈希表值转为列表返回代码实现Python解法二字符计数法最优解from typing import List class Solution: def groupAnagrams(self, strs: List[str]) - List[List[str]]: # 哈希表key字符计数元组value字母异位词列表 anagram_map {} for s in strs: # 初始化26位字母计数数组索引0~25分别对应小写字母a~z count [0] * 26 # 遍历字符统计每个字母出现次数 for char in s: # 计算字符对应索引从0开始计数保证小写字母映射无偏差 idx ord(char) - ord(a) count[idx] 1 # 列表不可哈希转为元组后作为字典键 key tuple(count) # 键不存在则初始化存在则追加 if key not in anagram_map: anagram_map[key] [] anagram_map[key].append(s) return list(anagram_map.values()) # 进阶简化写法可选用defaultdict省去判空逻辑 # from collections import defaultdict # class Solution: # def groupAnagrams(self, strs: List[str]) - List[List[str]]: # anagram_map defaultdict(list) # for s in strs: # count [0]*26 # for c in s: # count[ord(c)-ord(a)] 1 # anagram_map[tuple(count)].append(s) # return list(anagram_map.values()) # 本地测试 if __name__ __main__: sol Solution() print(sol.groupAnagrams([eat, tea, tan, ate, nat, bat]))执行过程演示以 “eat” 为例索引从0开始计数初始化计数列表[0,0,0,...,0]共26个0对应a-z字符 ‘e’ 对应索引ord(e)-ord(a)4→count[4] 1→[0,0,0,0,1,0,...0]字符 ‘a’ 对应索引ord(a)-ord(a)0→count[0] 1→[1,0,0,0,1,0,...0]字符 ‘t’ 对应索引ord(t)-ord(a)19→count[19] 1→[1,0,0,0,1,0,...,1,...0]转换为元组作为键“tea” 和 “ate” 会生成完全相同的键自动归为一组复杂度分析时间复杂度O ( n k ) O(nk)O(nk)仅需线性遍历数组所有字符无排序等高耗时操作遍历效率拉满空间复杂度O ( n k ) O(nk)O(nk)额外开销来自哈希表存储和固定大小的计数数组不计返回结果空间消耗合理优缺点✅ 优点时间最优无排序开销全场景适配稳定性极强✅ 优点特征键唯一性拉满完全规避排序潜在问题面试首选❌ 缺点代码逻辑稍复杂需理解字符编码与计数转换逻辑三、核心注意事项与易错点空字符串处理空字符串无字符计数列表全0排序后为空串可正常单独分组无需额外判断哈希键类型禁忌Python列表不可作为字典键计数列表必须转元组排序后字符列表必须用join拼接为字符串否则代码直接报错字符索引计算通过ord(char)-ord(a)映射0-25索引严格对应小写字母无索引越界风险返回格式规范字典values()为视图对象必须用list()强转才能得到题目要求的二维列表格式四、两种解法性能对比解法类型时间复杂度空间复杂度适用场景推荐指数排序法O ( n k log k ) O(nk\log k)O(nklogk)O ( n k ) O(nk)O(nk)字符串较短、追求代码简洁、快速入门⭐⭐⭐⭐字符计数法O ( n k ) O(nk)O(nk)O ( n k ) O(nk)O(nk)全场景、面试答题、大规模数据处理⭐⭐⭐⭐⭐五、全文总结与思考延伸5.1 全文总结本题核心考点哈希表键值设计、字符串特征提取、分组算法实现是哈希表实战的经典入门题型排序法适合入门理解代码简洁但时间复杂度偏高适合小规模数据场景字符计数法是本题最优解通过空间换时间时间复杂度优化至O(nk)面试务必优先使用同类分组题型均可借鉴该思路提取统一特征作为键借助哈希表实现高效分组通用性极强。5.2 思考延伸通用场景适配若字符串包含Unicode字符而非仅小写字母排序法仍通用直接按字符排序计数法可改用collections.Counter统计字符频次再转为元组作为键。代码进阶写法Python中可使用defaultdict(list)省去键不存在的判空逻辑简化代码适合熟练后使用基础学习阶段保留显式判断更易理解。刷题延伸吃透本题后可练习 LeetCode 242.有效的字母异位词基础前置题、LeetCode 438.找到字符串中所有字母异位词进阶题巩固字符计数与哈希表用法。
