【LeetCode面试150】——49字母异位分词
博客昵称：沈小农学编程
作者简介：一名在读硕士，定期更新相关算法面试题，欢迎关注小弟！
PS：哈喽！各位CSDN的uu们，我是你的小弟沈小农，希望我的文章能帮助到你。欢迎大家在评论区唠嗑指正，觉得好的话别忘了一键三连哦！😘
题目难度：中等
默认优化目标：最小化时间复杂度。
Python默认为Python3。
目录
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]*26
for ch in st:
counts[ord(ch)-ord('a')]+=1
#需要将list转换成tuple才能进行哈希
mp[tuple(counts)].append(st)
return list(mp.values())参考文献
原文地址：https://blog.csdn.net/Junmo12345/article/details/143881991
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！