【LeetCode面试150】——49字母异位分词

2025/11/20 3:49:19 来源：https://blog.csdn.net/Junmo12345/article/details/143881991 浏览: 次关键词：【LeetCode面试150】——49字母异位分词

博客昵称：沈小农学编程

作者简介：一名在读硕士，定期更新相关算法面试题，欢迎关注小弟！

PS：哈喽！各位CSDN的uu们，我是你的小弟沈小农，希望我的文章能帮助到你。欢迎大家在评论区唠嗑指正，觉得好的话别忘了一键三连哦！😘

题目难度：中等

默认优化目标：最小化时间复杂度。

Python默认为Python3。

1 题目描述

2 题目解析

3 算法框架及程序实现

3.1 哈希表+排序

3.2 哈希表+计数

参考文献

1 题目描述

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

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

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

提示：

1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

2 题目解析

异位等价于两个字符串中各字符出现的次数相等，或者经过排序后相等。同一组异位词，可以只用其中一个词与别的词进行判断，它们互为异位词则它与这组的所有词互为异位词。

输入是一个字符串数组strs，输出是字符串数组ans。

3 算法框架及程序实现

3.1 哈希表+排序

使用排序好后的字符串作为哈希表的键值，将异位词添加到相应的key后面。

时间复杂度O(nk*log k)，空间复杂度O(nk)。n为strs长度，k为strs中最长字符串长度。

C++代码实现

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string,vector<string>> mp;for(string& str:strs){string key=str;sort(key.begin(),key.end());mp[key].push_back(str);}vector<vector<string>> ans;for(auto it=mp.begin();it!=mp.end();it++){ans.push_back(it->second);}return ans;}
};

Python代码实现

class Solution:def groupAnagrams(self, strs: List[str]) -> List[List[str]]:mp=collections.defaultdict(list)
for st in strs:key="".join(sorted(st))mp[key].append(st)
return list(mp.values())

3.2 哈希表+计数

对strs的每一个字符串创造一个哈希表来记录字符出现次数，把这个次数哈希表作为键值，插入异位词。

时间复杂度O(n(k+26))，空间复杂度O(n(k+26))。

C++代码实现

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {auto arrayHash=[fn=hash<int>{}](const array<int,26>& arr)->size_t{return accumulate(arr.begin(),arr.end(),0u,[&](size_t acc, int num){return(acc<<1)^fn(num);});};unordered_map<array<int,26>,vector<string>,decltype(arrayHash)>mp(0,arrayHash);for(string& str:strs){array<int,26> counts{};int length=str.length();for(int i=0;i<length;i++){counts[str[i]-'a']++;}mp[counts].push_back(str);}vector<vector<string>> ans;for(auto it=mp.begin();it!=mp.end();it++){ans.push_back(it->second);}return ans;}
};

Python代码实现

class Solution:def groupAnagrams(self, strs: List[str]) -> List[List[str]]:mp=collections.defaultdict(list)
for st in strs:counts=[0]*26for ch in st:counts[ord(ch)-ord('a')]+=1#需要将list转换成tuple才能进行哈希mp[tuple(counts)].append(st)
return list(mp.values())