编程题-字母异位词分组（中等-重点）

题目：

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

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

解法一（for循环遍历-时间复杂度超限）：

由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序后的字符串作为哈希表的键。

依次遍历strs中的每个元素，通过建立unordered_map<string, int>哈希表对新添加的strs的元素和strs中的其他元素执行for循环进行判断比较，在for循环中对与指定strs的元素相同的字母异位词进行添加，与指定strs元素不同的字母异位词跳过，并删除for循环遍历后的与指定strs元素相同的字母异位词的组合，进入下一个for循环判断另一个strs指定元素的字母异位词。其中默认strs中的第一个元素为指定的本方法时间复杂度超限仅与下面的方法作为参考，并不是本题的正确解，如下为笔者代码：

class Solution {
public:
    void kyk(vector<string> strs, vector<vector<string>>& results, vector<string> result){
        int length = strs.size();
        if(length==0){
            return;
        }
        stack<int> intStack1;
        intStack1.push(0);
        result.push_back(strs[0]);
        for(int i=1; i<length; i++){
            unordered_map<string,int> hashTable;
            string str1 = strs[0];
            string str2 = strs[i];
            sort(str1.begin(),str1.end());
            sort(str2.begin(),str2.end());
            hashTable[str1]++;
            auto it = hashTable.find(str2);
            if(it!=hashTable.end()){
                intStack1.push(i);
                result.push_back(strs[i]);
            }
        }
        while(!intStack1.empty()){
            int index = intStack1.top();
            strs.erase(strs.begin() + index);
            intStack1.pop();
        }
        results.push_back(result);
        result = {};
        kyk(strs, results, result);
    }
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> results;
        vector<string> result;
        int length = strs.size();
        kyk(strs, results, result);
        return results;
    }
};

解法二（排序+高阶哈希表使用）：

上述方法使用sort排序方法和unordered_map<string, int>哈希表对字母异位词进行分组判断，但是在进行for循环遍历时会导致数组元素的重复访问，导致时间复杂度升到，因此为了防止数组元素的重复访问，我们采用unordered_map<string, vector<string>>高阶的哈希表数据结果来降低时间复杂度，其中哈希表存储每一组字母异位词，哈希表的键为一组字母异位词的标志，哈希表的值为一组字母异位词列表。

遍历每个字符串，对于每个字符串，得到该字符串所在的一组字母异位词的标志，将当前字符串加入改组字母异位次的列表中。遍历全部字符串后，哈希表中的每个键值对即为一组字母异位词。如下为实现代码：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        创建高阶哈希表数据结构，其中键为一组字母异位词的标志，值为一组字母异位词的列表。
        unordered_map<string, vector<string>> mp;
        //一次遍历实现所有字母异位词添加到mp高阶哈希表中
        for (string& str: strs) {
            string key = str;
            sort(key.begin(), key.end());
            mp[key].emplace_back(str);
        }
        //for循环访问高阶哈希表中所有元素，并将其添加到ans最终返回结果中
        vector<vector<string>> ans;
        for (auto it = mp.begin(); it != mp.end(); ++it) {
            ans.emplace_back(it->second);
        }
        return ans;
    }
};

上述方法仅执行了单层的for循环，并没有嵌套多层for循环。因此时间复杂度：O(nklogk)，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。需要遍历 n 个字符串，对于每个字符串，需要 O(klogk) 的时间进行排序以及 O(1) 的时间更新哈希表，因此总时间复杂度是 O(nklogk)。空间复杂度：O(nk)，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。需要用哈希表存储全部字符串。

解法三（计数+高阶哈希表）：

由于互为字母异位词的两个字符串包含的字母相同，因此除了上述采用排序的方式确定两个字母异位词是否是相同的方式之外，也可以通过计数两个字符串中相同字母出现的次数来进行判断，将每个字母出现的次数使用字符串表示，作为哈希表的键。

由于字符串只包含小写字母，因此对于每个字符串，可以使用长度为26的数组记录每个字母出现的次数。需要注意的是，在使用数组作为哈希表的键时，不同语言的支持程度不同，因此不同语言的实现方式也不同。如下为实现代码：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // 自定义对 array<int, 26> 类型的哈希函数
        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].emplace_back(str);
        }
        vector<vector<string>> ans;
        for (auto it = mp.begin(); it != mp.end(); ++it) {
            ans.emplace_back(it->second);
        }
        return ans;
    }
};

时间复杂度：O(n(k+∣Σ∣))，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度，Σ 是字符集，在本题中字符集为所有小写字母，∣Σ∣=26。需要遍历 n 个字符串，对于每个字符串，需要 O(k) 的时间计算每个字母出现的次数，O(∣Σ∣) 的时间生成哈希表的键，以及 O(1) 的时间更新哈希表，因此总时间复杂度是 O(n(k+∣Σ∣))。空间复杂度：O(n(k+∣Σ∣))，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的最大长度，Σ 是字符集，在本题中字符集为所有小写字母，∣Σ∣=26。需要用哈希表存储全部字符串，而记录每个字符串中每个字母出现次数的数组需要的空间为 O(∣Σ∣)，在渐进意义下小于 O(n(k+∣Σ∣))，可以忽略不计。