[LeetCode] Group Anagrams

https://leetcode.com/problems/anagrams/

对每个string求个“hash”，存入hash table，对应的value是group的id。每遇到一个string，用同样的方法计算hash，如果出现过，就加入相应的group；否则，就加入hash table并新开一个group

/*
 * author  : TK
 * date    : 2017-02-16
 * problem : LeetCode 49. Group Anagrams
 * method  : Hash Table.
 * language: C++
 */

// Compute a hash value of every string and put it into the corresponding group.
// In the following code, the "hash value" is the lexicographical order of a string.
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector< vector<string> > ret;
        unordered_map<string, int> map;
        int idx = 0;
        for (int i = 0; i < strs.size(); ++i) {
            string str = strs[i];
            sort(str.begin(), str.end());
            if (map.find(str) != map.end()) {
                ret[map[str]].push_back(strs[i]);
            } else {
                map[str] = idx++;
                vector<string> new_vec(1, strs[i]);
                ret.push_back(new_vec);
            }
        }
        return ret;
    }
};

由于所有的字母都是小写，上面的排序可以用计数排序优化到O(n)。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector< vector<string> > ret;
        unordered_map<string, int> map;
        int idx = 0;
        for (int i = 0; i < strs.size(); ++i) {
            string str = strs[i];
            counting_sort(str);
            if (map.find(str) != map.end()) {
                ret[map[str]].push_back(strs[i]);
            } else {
                map[str] = idx++;
                vector<string> new_vec(1, strs[i]);
                ret.push_back(new_vec);
            }
        }
        return ret;
    }
private:
    void counting_sort(string& str) {
        vector<int> number(26, 0);
        for (int i = 0; i < str.size(); ++i) {
            number[str[i] - 'a']++;
        }
        for (int i = 0; i < str.size(); ++i) {
            for (int j = 0; j < 26; ++j) {
                if (number[j] > 0) {
                    str[i] = (char)('a' + j);
                    number[j]--;
                    break;
                }
            }
        }
    }
};