49. Group Anagrams

O(nk) time
这道题考如何hash
followup是MapReduce

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        d = defaultdict(list)
        for s in strs:
            f = [0] * 26
            for c in s:
                f[ord(c) - ord('a')] += 1
            d[tuple(f)].append(s)
        return d.values()

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        def myhash(s): # 'bcabe' -> '1a2b1c1e'
            f = [0] * 26
            for c in s:
                f[ord(c) - ord('a')] += 1
            res = ''
            for i, cnt in enumerate(f):
                if cnt > 0:
                    res += str(cnt) + chr(ord('a') + i)
            return res
        d = defaultdict(list)
        for s in strs:
            d[myhash(s)].append(s)
        return d.values()

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        def myhash(s): # 'bcabe' -> '1 2 1 0 1 0 ... 0'
            f = [0] * 26
            for c in s:
                f[ord(c) - ord('a')] += 1
            res = ''
            return ' '.join(map(str, f))
        d = defaultdict(list)
        for s in strs:
            d[myhash(s)].append(s)
        return d.values()

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> m;
        for (const auto &s : strs) {
            m[hash(s)].push_back(s);
        }
        vector<vector<string>> res;
        for (const auto &p : m) {
            res.push_back(p.second);
        }
        return res;
    }

    string hash(const string &s) { // bucket sort
        int f[26] = {0};
        for (char c : s) {
            ++f[c - 'a'];
        }
        string res;
        for (int x : f) {
            res += to_string(x);
            res += ' ';
        }
        return res;
    }
};

普通解法 O(nklogk) time

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        d = defaultdict(list)
        for s in strs:
            d[''.join(sorted(s))].append(s) # key是一个str: 'bcabe' -> 'abbce'
            # d[tuple(sorted(s))].append(s) # key是一个tuple: 'bcabe' -> ('a', 'b', 'b', 'c', 'e')
        return d.values()

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> hm;
        for (const auto &s : strs) {
            hm[key(s)].push_back(s);
        }
        vector<vector<string>> res;
        for (const auto &p : hm) {
            res.push_back(p.second);
        }
        return res;
    }

    string key(string s) {
        sort(s.begin(), s.end());
        return s;
    }
};

const int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<long, vector<string> > hash_map;
        for (auto &&str : strs)
            hash_map[key(str)].push_back(str);
        vector<vector<string> > ret(hash_map.size());
        size_t i(0);
        for (auto &&pair : hash_map) {
            ret[i].swap(pair.second);
            sort(ret[i].begin(), ret[i].end());
            ++i;
        }
        return ret;
    }

private:
    long key(const string &str) {
        long ret(1);
        for (auto &&c : str)
            ret *= primes[c - 'a'];
        return ret;
    }
};