leetcode-49. Group Anagrams 字母異位詞分組

Given an array of strings, group anagrams together. Example: Input: ["eat", "tea", "tan", "ate", "nat", "bat"] , Output: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] Note: All inputs will be in lowercase. The order of your output does not matter.

給定一個字元串數組，将字母異位詞組合在一起。字母異位詞指字母相同，但排列不同的字元串。 示例: 輸入: ["eat", "tea", "tan", "ate", "nat", "bat"] , 輸出: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] 說明： 所有輸入均為小寫字母。 不考慮答案輸出的順序。

思路：

第一種：對每個字元 串的字母排序，如果結果相等，那就是一樣的，将原始 字元串加入哈希表中。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map<string,vector<string>> mp;
        for(string s:strs)
        {
            string t=s;    //周遊strs中每一個字元串
            sort(t.begin(),t.end());    //對每個字元串的字元排序
            mp[t].push_back(s);    //将相等的字元串加入哈希表
        }
        for(auto m:mp)
            res.push_back(m.second);    //将哈希表的value給res
        return res;
    }
};
           

第二種： 不用對每個字元串排序，用一個a[26]的數組映射 每個字元串中每個字元出現的次數。然後a數組 相等的字元串 就是一組，加入 同一個哈希表中。比較a數組相等 可以周遊是否相等，或者将其轉為一個特定字元串，比較字元串是否相等。速度慢

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map<string,vector<string>> mp;
        for(string s:strs)
        {
            vector<int> vec(26,0);
            for(char c:s) vec[c-'a']++;
            string t="";
            for(int i:vec) t+=to_string(i)+"/";   #将映射數組轉為唯一的字元串
            mp[t].push_back(s);
        }
        for(auto m:mp)
            res.push_back(m.second);
        return res;
    }
};