Group-Anagrams

LeetCode

第22天，今天刷回了Medium，果然这个难度才适合我。

Given an array of strings, group anagrams together.

For example, given: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
Return:

1
2
3
4
5
[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note: All inputs will be in lower-case.

题目很简短，主要的难点是怎样判断两个字符串是同组的（即s1是s2的一个置换），我的想法是利用hash来区分，不过这个hash函数写起来就比较麻烦了，主要是要考虑碰撞：

1
2
3
4
5
6
7
8
9
10
unsigned hashString(string &s) {
    int sum = 1;
    int count[26]{0};
    for(auto c:s)
        count[c-'a']++;
    for(int i = 0;i < 26;i++){
        sum = sum*133 + count[i];
    }
    return sum;
}

然后就是一些细节问题了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<vector<string>> groupAnagrams(vector<string>& strs) {
    vector<vector<string> > ret;
    unordered_map<unsigned,int> mRet;
    int now = 0;
    for(auto &s:strs) {
        unsigned h = hashString(s);
        cout << h << endl;
        if (mRet.find(h) == mRet.end()){
            ret.push_back({});
            mRet[h] = now;
            now++;
        }
        ret[mRet[h]].push_back(s);
    }
    return ret;
}

dicuss中有另外一种hash的方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static List<List<String>> groupAnagrams(String[] strs) { 
   int[] prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103};//最多10609个z
            List<List<String>> res = new ArrayList<>();
            HashMap<Integer, Integer> map = new HashMap<>();
            for (String s : strs) {
                int key = 1;
                for (char c : s.toCharArray()) {
                    key *= prime[c - 'a'];
                }
                List<String> t;
                if (map.containsKey(key)) {
                    t = res.get(map.get(key));
                } else {
                    t = new ArrayList<>();
                    res.add(t);
                    map.put(key, res.size() - 1);
                }
                t.add(s);
            }
            return res;
    }

额，说实话，里面的数学依据我没看懂，是因为素数只能被1和它本身整除吗？

然后同样是在dicuss中看到的，对字符串sort来判断是否在同一组的方法：

1
2
3
4
5
6
7
8
9
10
11
vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string> > anagrams;
    for (string s: strs) {
        string sorted = s;
        sort(sorted.begin(), sorted.end());
        anagrams[sorted].push_back(s);
    }
    vector<vector<string> > res;
    for (auto p: anagrams) res.push_back(p.second);
    return res;
}

没想到这道题还有solution,里面有两个方法，一个是用sort的，和上面的差不多。另一个有趣点，通过计数来生成一个新的字符串，然后在hash:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<List<String>> groupAnagrams(String[] strs) {
    if (strs.length == 0) return new ArrayList();
    Map<String, List> ans = new HashMap<String, List>();
    int[] count = new int[26];
    for (String s : strs) {
        Arrays.fill(count, 0);
        for (char c : s.toCharArray()) count[c - 'a']++;

        StringBuilder sb = new StringBuilder("");
        for (int i = 0; i < 26; i++) {
            sb.append('#');
            sb.append(count[i]);
        }
        String key = sb.toString();
        if (!ans.containsKey(key)) ans.put(key, new ArrayList());
        ans.get(key).add(s);
    }
    return new ArrayList(ans.values());
}