LeetCode-49. 字母异位词分组

本是古典何须时尚 2022-03-14 10:50 165阅读 0赞

# [49. 字母异位词分组][49.] #

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

示例:

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

说明：

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

### 哈希表 ###

虽然过了，但不足的地方在于最后vec空间的处理，因为vector不预先分配空间，无法使用下标法的，所以先分足够的空间，再最后重新分配空间。

static const int _ = []() { 
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        return 0;
    }();
    class Solution { 
    public:
        vector<vector<string>> groupAnagrams(vector<string>& strs) { 
            unordered_map<string,int> mp;
            vector<vector<string>> vec(strs.size());
            int k=0;
            for(int i=0;i<strs.size();i++)
            { 
                string ss = strs[i];
                sort(ss.begin(),ss.end());
                if(mp.count(ss)==0)
                { 
                    mp[ss]=k;
                    k++;
                }
                vec[mp[ss]].push_back(strs[i]);
            }
            vec.resize(k);
            return vec;
        }
    };

### 改良 ###

这里对哈希表做了改良，改良后的哈希表表现形式应该是这样的:

mp["abc"] = { "abc","bac","cba"};
    mp["tea"] = { "tea","tae","ate"};
    ...

static const int _ = []() { 
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        return 0;
    }();
    class Solution { 
    public:
        vector<vector<string>> groupAnagrams(vector<string>& strs) { 
            unordered_map<string,vector<string>> mp;
            vector<vector<string>> vec;
            for(auto r:strs)
            { 
                string s(r);
                sort(s.begin(),s.end());
                mp[s].push_back(r);
            }
            for(auto p:mp)
            { 
                vec.push_back(p.second);
            }
            return vec;
        }
    };

[49.]: https://leetcode-cn.com/problems/group-anagrams/