Group String

发表于 | 分类于

Group String

题目描述：

给定一组字符串序列，将含有相同字符的字符串进行分组。我们以”eat”和”ate”是同一组字符串

例子：

见LeetCode49

解题思路：

我们通过对vector中字符串进行构建哈希表，利用该哈希表作为key，字符串作为value来进行查找和匹配；而后对最终哈希表中的所有value进行保存即为分组的结果。

代码如下：

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
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        map<map<char, int>, vector<string>> hash;
        vector<vector<string>> res;
        map<char, int> str_map;
        for (int i = 0; i < strs.size(); i++){
            str_map = generate(strs[i]);
            //对每个字符串产生哈希表
            if (hash.find(str_map) == hash.end()){
                vector<string> tmp = {strs[i]};
                hash.insert({str_map, tmp});
                //如果结果哈希表中还未出现
            }else{
                hash[str_map].push_back(strs[i]);
                //如果已经出现
            }
        }
        map<map<char, int>, vector<string>> :: iterator it = hash.begin();
        while(it != hash.end()){
            res.push_back(it->second);
            it++;
            //将结果哈希表中的value进行保存即为分组结果
        }
        return res;
    }
    map<char, int> generate(string str){
    //对字符串进行构建哈希表操作
        map<char, int> hash;
        for (int i = 0; i < str.size(); i++){
            if (hash.find(str[i]) == hash.end()){
                hash.insert({str[i], 1});
            }else{
                hash[str[i]]++;
            }
        }
        return hash;
    }
};