字母异位词分组

字母异位词分组

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

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

示例 1:

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

解题思路：

• 1 暴力解法(时间复杂度O(n^2))：两层for循环使用哈希表进行判断是否为字母异位词，是则加入结果中。
• 2 对字符串进行排序后使用哈希表

暴力解法

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int size = strs.size();
        vector<vector<string>> result;
        vector<bool> visited(size, false);
        for (int i=0; i<size; i++){
            if (visited[i]) continue;
            visited[i] = true;
            vector<string> path;
            path.push_back(strs[i]);
            unordered_map<char, int> my_map;
            for(auto c:strs[i]) my_map[c]++;
            for(int j=i+1; j<size; j++){
                if (visited[j]) continue;
                unordered_map<char, int> temp;
                for(auto c:strs[j]) temp[c]++;
                if (temp == my_map){
                    path.push_back(strs[j]);
                    visited[j] = true;
                }
            }
            result.push_back(path);
        }
        return result;
    }
};

对字符串进行排序后使用哈希表

• 1 哈希表的设计<string, vector<string>>
• 2 哈希表的遍历 for(auto [key, value] : map)

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int size = strs.size();
        vector<vector<string>> result;
        unordered_map<string, vector<string>> my_map;
        for (int i=0; i<size; i++){
            string sort_s = strs[i];
            sort(sort_s.begin(), sort_s.end());
            my_map[sort_s].push_back(strs[i]);
        }
        for(auto [key, value] : my_map)
            result.push_back(value);
        return result;
    }
};