题目

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

输入:

["eat", "tea", "tan", "ate", "nat", "bat"],

输出:

[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

说明：

所有输入均为小写字母。不考虑答案输出的顺序。

Attempt One

基本想法是将每个单词中的字母排序，结果存入字典(map)中。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string> &strs) {
        vector<vector<string>> result;
        map<string, int> dict;
        for (auto s : strs) {
            string w = s;
            sort(w.begin(), w.end());
            if (dict.find(w) == dict.end()) {
                vector<string> v;
                v.push_back(s);
                result.push_back(v);
                dict[w] = result.size() - 1;
            } else {
                result[dict[w]].push_back(s);
            }
        }
        //for (auto &row : result)
        //    sort(row.begin(), row.end());
        return result;
    }
}

结果：Runtime 56ms 28%

优化

上面中间过程生成临时的vector，优化思路去掉这个中间过程，

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) 
    {
        vector<vector<string>> result;
        result.reserve(strs.size());
		
        unordered_map<string, vector<string>*> dict;
        
        for(int i { 0 }; i < strs.size(); ++i) {
            string w = strs[i];
            sort(w.begin(), w.end());
            
            if(dict.find(w) != dict.end()) {
                dict[w]->push_back(strs[i]);
            } else {
                result.push_back( {strs[i]} );
                dict[w] = &result[(result.size() - 1)];
            }
        }
        
        return result;
    }
}

结果：Runtime 36ms 91%，有明显改善。

Hash 法

另外一种想法就是 Hash 散列，一个字母对应一个质数，将一个单词中所有字母换成质数想乘，得到 Hash 值。

 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

class Solution {
public:
    long long int primeNumber[26] { 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97, 101 };
    vector<vector<string>> groupAnagrams4(vector<string>& strs) 
    {
        vector<vector<string>> result;
        result.reserve(strs.size());
		
        unordered_map<unsigned long long, vector<string>*> dict;
        unsigned long long hashValue { 1 };
        
        for(int i { 0 }; i < strs.size(); ++i) {
            hashValue = 1;
            
            for(int j { 0 }; j < strs[i].size(); ++j) {
                hashValue = hashValue * primeNumber[(strs[i][j] - 'a')];
            }
            
            if(dict.find(hashValue) != dict.end()) {
                dict[hashValue]->push_back(strs[i]);
            } else {
                result.push_back( {strs[i]} );
                dict[hashValue] = &result[(result.size() - 1)];
            }
        }
        
        return result;
    }
}

结果： Runtime 28ms 99%