題目： LeetCode - 49. Group Anagrams

題目說明

給一個字串的陣列，將所有組成字串的字母相同的放在一起。

解題思路

  • 想法：可使用 sort() 來排序 String，若是兩個組成字串的字母一樣，那排序過後會長的一樣。

  • 解法一：使用 vector<pair<string, int>> 存放資料 ( 後面稱作 temp )，first 放排序過的字串，second 放該字串在 strs 裡面的 index。之後對 temp 進行排序 ( 預設會排序 first )。最後將排序過後相同的字串存入 res 即可。

  • 解法二：使用 unordered_map<string, vector<string>> 存放資料，key 存放排序過後的字串，value 存放未排序的字串，最後將 value 存入 res 即可。

參考解法

解法一：

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
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        vector<pair<string, int>> temp;
        string stemp;

        for (int i = 0; i < strs.size(); ++i)
        {
            stemp = strs[i];
            sort(stemp.begin(), stemp.end());
            temp.push_back(make_pair(stemp, i));
        }

        sort(temp.begin(), temp.end());

        stemp = temp[0].first;
        vector<string> vtemp;

        for (int i = 0; i < temp.size(); ++i)
        {
            if (stemp == temp[i].first)
                vtemp.push_back(strs[temp[i].second]);
            else
            {
                res.push_back(vtemp);
                vtemp.clear();
                stemp = temp[i].first;
                vtemp.push_back(strs[temp[i].second]);
            }
        }
        res.push_back(vtemp);

        return res;
    }
};

解法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> v;
        unordered_map<string, vector<string>> _m;
        for(auto s : strs)
        {
            string tmp = s;
            sort(tmp.begin(), tmp.end());
            _m[tmp].push_back(s);
        }
        for(auto m : _m) v.push_back(m.second);
        return v;
    }
};