49.字母异位词分组

无重复字符的最大子串

一眼就是使用哈希来做，python的话就是字典。
我第一想到的是用counter分别计算每个单词的counter然后找相同的。
这个思路是错误的，因为需要一个标记visited的数组并且需要反复多次遍历。

正解

注意到每个字母异位词实际上是sort之后相同的词汇。不妨把单词sorted之后得到的东西作为key，把原单词加入进value。

python

from collections import defaultdict
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dict = defaultdict(list)
        for word in strs:
            sorted_word = "".join(sorted(word))
            dict[sorted_word].append(word)
        return list(dict.values())

C++

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> m;
        for (string& s : strs) {
            string sorted_s = s;
            ranges::sort(sorted_s); // 把 s 排序，作为哈希表的 key
            m[sorted_s].push_back(s); // 排序后相同的字符串分到同一组
        }
        vector<vector<string>> ans;
        ans.reserve(m.size()); // 预分配空间
        for (auto& [_, value] : m) {
            ans.push_back(value); // 哈希表的 value 保存分组后的结果
        }
        return ans;
    }
};

复杂度分析

时间复杂度：O(nmlogm)，其中 n 为 strs 的长度，m 为 strs[i] 的长度。每个字符串排序需要 O(mlogm) 的时间。我们有 n 个字符串，所以总的时间复杂度为 O(nmlogm)。
空间复杂度：O(nm)。