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.

---

Anagrams是指颠倒字母而成的字，比如ate和eat，颠倒字母包括随意乱序颠倒，比如nat和tan。
本题要求把所有anagrams分组找出来，思路是对每个单词内部排序，然后对排序完的所有单词再外部排序，这样相同的anagrams就会排在一起，只要把anagrams相同的放在一个group就可以。比如ate、eat、tea都内部排序成aet，然后3个aet外部排序时会排在一起，这样就能把ate、eat、tea组合成一个group。

完整代码如下：

struct Word {
    string key, value;
    bool operator<(const Word& w) { return this->key < w.key; }
};
class Solution {
public:
    vector<vector<string> > groupAnagrams(vector<string>& strs)
    {
        vector<Word> words;
        for (int i = 0; i < strs.size(); i++) {
            Word tmp;
            tmp.value = strs[i];
            sort(strs[i].begin(), strs[i].end());
            tmp.key = strs[i];
            words.push_back(tmp);
        }
        sort(words.begin(), words.end());
        vector<string> group;
        vector<vector<string> > ans;
        group.push_back(words[0].value);
        for (int i = 1; i < words.size(); i++) {
            if (words[i].key == words[i – 1].key) {
                group.push_back(words[i].value);
            }
            else {
                ans.push_back(group);
                group.clear();
                group.push_back(words[i].value);
            }
        }
        ans.push_back(group);
        return ans;
    }
};

本代码提交AC，用时64MS。

二刷。不自定义数据结构，使用map<string, vector<string=””>>，完整代码如下：

class Solution {
public:
    vector<vector<string> > groupAnagrams(vector<string>& strs)
    {
        unordered_map<string, vector<string> > hash;
        for (const auto& s : strs) {
            string tmp = s;
            sort(tmp.begin(), tmp.end());
            hash[tmp].push_back(s);
        }
        vector<vector<string> > ans;
        for (const auto& it : hash) {
            ans.push_back(it.second);
        }
        return ans;
    }
};

本代码提交AC，用时26MS。