Code & Func

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

Given an array of strings, group anagrams together.

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

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

Note: All inputs will be in lower-case.

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

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

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

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

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

1
public static List<List<String>> groupAnagrams(String[] strs) {
2
   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
3
            List<List<String>> res = new ArrayList<>();
4
            HashMap<Integer, Integer> map = new HashMap<>();
5
            for (String s : strs) {
6
                int key = 1;
7
                for (char c : s.toCharArray()) {
8
                    key *= prime[c - 'a'];
9
                }
10
                List<String> t;
11
                if (map.containsKey(key)) {
12
                    t = res.get(map.get(key));
13
                } else {
14
                    t = new ArrayList<>();
15
                    res.add(t);
6 collapsed lines
16
                    map.put(key, res.size() - 1);
17
                }
18
                t.add(s);
19
            }
20
            return res;
21
    }

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

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

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

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

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

9
        StringBuilder sb = new StringBuilder("");
10
        for (int i = 0; i < 26; i++) {
11
            sb.append('#');
12
            sb.append(count[i]);
13
        }
14
        String key = sb.toString();
15
        if (!ans.containsKey(key)) ans.put(key, new ArrayList());
4 collapsed lines
16
        ans.get(key).add(s);
17
    }
18
    return new ArrayList(ans.values());
19
}