跳转至

49 字母异位词分组

本题本质上是对哈希函数的考察

如何设计哈希函数,让字母异位词指向同一个key值,通过value值将这些字母异位词收集起来

由以上分析,我们判断使用unordered_map

做法一

第一种做法:对字符串进行排序,同一组异位词排序后的结果一定相同

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // 每个排序后的key对应的乱序的str
        unordered_map<string, vector<string>> hashMap;
        for (string& str : strs) {
            string key = str;
            sort(key.begin(), key.end());
            hashMap[key].push_back(str);
        }
        vector<vector<string>> ans;
        for (auto it = hashMap.begin(); it != hashMap.end(); it++) {
            ans.push_back(it->second);
        }
        return ans;
    }
};

做法二

第二种做法:同一组异位词每个字符出现的次数一定相同

例如"abca"

key的设置为a2b1c1

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> map;
        for (string str : strs) {
            // 如果写成int counts[26];过不了
            // 可能是因为编译优化
            int counts[26] = {0};
            for (char c : str) {
                counts[c - 'a']++;
            }
            string key = "";
            for (int i = 0; i < 26; ++i) {
                if (counts[i]) {
                    key.push_back(i + 'a');
                    // 这一步不能漏
                    key.push_back(counts[i]);
                }
            }
            map[key].push_back(str);
        }
        vector<vector<string>> res;
        for (auto it = map.begin(); it != map.end(); it++) {
            res.push_back(it->second);
        }
        return res;
    }
};