字母异位词分组

发表于 分类于 ， 阅读次数： Waline： 本文字数： 1.9k 阅读时长 ≈ 2 分钟

49. 字母异位词分组

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

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例：

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

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

思路：

方法一：哈希 + 排序

由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string> > mp;
        for(string& str : strs){
            string key = str;
            sort(key.begin(), key.end());
            mp[key].push_back(str);
        }
        vector<vector<string> > res;
        for(auto it = mp.begin(); it != mp.end(); it++){
            res.emplace_back(it->second);
        }
        return res;
    }
};

方法二：哈希 + 计数

例如 aabbc

转化为 a2b2c1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string> > codeToGroup;
        for(string s : strs){
            string code = encode(s);
            codeToGroup[code].push_back(s);
        }
        vector<vector<string> > res;
        for (auto it = codeToGroup.begin(); it != codeToGroup.end(); ++it) {
            res.push_back(it->second);
        }
        return res;
    }
    //利用每个字符的出现次数进行编码
    string encode(string s){
        vector<int> code(26);
        for(char c : s){
            int delta = c - 'a';
            code[delta]++;
        }
        string res;
        for(int i = 0; i < 26; i++){
            if(code[i] != 0){
                res += (char)('a' + i) + to_string(code[i]);
            }
        }
        return res;
    }
};