分析

• 本题的考点：哈希表。

• 将每个排序后的字符串作为哈希表的键，然后将排序的字符串插入哈希表中，这样字母相同但排列不同的字符串会被放到一起。

代码

• C++

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {

        unordered_map<string, vector<string>> hash;
        for (auto &str : strs) {
            string s = str;
            sort(s.begin(), s.end());
            hash[s].push_back(str);
        }

        vector<vector<string>> res;
        for (auto &item : hash) res.push_back(item.second);

        return res;
    }
};

• Java

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {

        HashMap<String, List<String>> hash = new HashMap<>();
        for (String str : strs) {
            String t = sort(str);
            if (!hash.containsKey(t)) hash.put(t, new ArrayList<>());
            hash.get(t).add(str);
        }

        return new ArrayList<>(hash.values());
    }

    // 返回字符串s排序后的字符串
    private String sort(String s) {
        char[] chs = s.toCharArray();
        Arrays.sort(chs);
        return new String(chs);
    }
}

时空复杂度分析

• 时间复杂度：$O(n \times k \times \log k)$，其中n是strs中的字符串的数量，k是strs中的字符串的的最大长度。

• 空间复杂度：$O(n \times k)$。