【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]*26
            for ch in st:
                counts[ord(ch)-ord('a')]+=1
            #需要将list转换成tuple才能进行哈希
            mp[tuple(counts)].append(st)

        return list(mp.values())