题目描述

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

样例

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

算法1

(哈希 + 桶排序) $O(n * l)$

把输入中的单词，映射到哈希表中，异位词都映射成一个key即可。
算法1中，每个词对应的key是对其桶排序得到的字符串。

时间复杂度

一共要映射$n$个词，对于每个词，桶排序时间复杂度为字符串长度的级别$O(l)$；
将哈希表整理成结果，复杂度也为$O(n * l)$；
总复杂度即为$O(n * l)$

参考文献

C++ 代码

class Solution {
private:
    unordered_map<string, vector<string>> hash;
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        if (strs.empty()) return {};
        for (string str: strs){
            helper(str);
        }

        vector<vector<string>> res; 
        for (auto k_v: hash){
            res.push_back(k_v.second);
        }

        return res;
    }

    void helper(string &s){
        vector<int> cnt(26);
        for (char c: s) ++cnt[c - 'a'];

        string key;
        for (int i = 0; i < 26; ++i) key += string(cnt[i], 'a' + i);

        hash[key].push_back(s);
    }
};

算法2

(哈希 + 快速排序) $O(n * llogl)$

把输入中的单词，映射到哈希表中，异位词都映射成一个key即可。
算法1中，每个词对应的key是对其快速排序得到的字符串。

时间复杂度

一共要映射$n$个词，对于每个词，桶排序时间复杂度为字符串长度的级别$O(llogl)$；
将哈希表整理成结果，复杂度为$O(n * l)$；
总复杂度即为$O(n * llogl)$

参考文献

C++ 代码

class Solution {
private:
    unordered_map<string, vector<string>> hash;
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        if (strs.empty()) return {};
        for (string str: strs){
            string tmp = str;
            sort(tmp.begin(), tmp.end());
            hash[tmp].push_back(str);
        }

        vector<vector<string>> res; 
        for (auto k_v: hash){
            res.push_back(k_v.second);
        }

        return res;
    }
};