姓名：毛浩 学号：17029250003

【嵌牛导读】一道力扣题。

【嵌牛鼻子】力扣

【嵌牛提问】如何解决同位异构词

【嵌牛正文】

力扣49题:Group Anagrams

@(leetcode)[数组|哈希表|字符串]

---

题意回顾

先放上题目链接。

49.png

这道题的本质就是一个异位词的分组，那我们该怎样构想一种给予异位词统一标识的方法呢？

方法一

我们很容易想到异位词经过排序后的形式是一致的，都是按照从小到大的字母顺序排列的，因此我们可以将一个词经过排序后的字符串形式作为这类异位词的标签，在接下来的遍历中，我们只要按照这种标识方法对每个词进行分类即可完成题意。

我第一次写的代码

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        if(!strs.size())    return {};
        unordered_map<string, int> dic;
        vector<vector<string>> res;
        int cnt = 0;
        for(auto s:strs){
            string tmp = s;
            sort(tmp.begin(), tmp.end());
            if(dic.find(tmp) != dic.end()){
                res[dic[tmp]].push_back(s);
            }
            else{
                dic[tmp] = cnt++;
                vector<string> v;
                v.push_back(s);
                res.push_back(v);
            }
        }
        return res;
    }
};

代码可以AC，只是这样的代码看上去有些不够漂亮！
于是我看了评论区用相同方法的朋友，看见了一种非常干净的写法！！

改进后的代码

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

这里直接将vector作为哈希表的值，这是我第一次看见这样的用法，so amazing（偷偷拿小本本记下！）

方法二

其实还有一种非常容易就能想到的标识方法。因为对于两个异位词，它们是由相同并等量的字母组成，只是排列顺序不同而已。因此，我们只要对26个字母进行统计，拥有相同且等量的字符串我们就可以将其归结为同一类异位词。

代码

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map<string, vector<string>> m;
        vector<int> a(26);
        for(auto s:strs){
            a.assign(26, 0);
            for(auto c:s){
                a[c-'a']++;
            }
            string tmp;
            for(int i=0; i<26; i++){
                tmp += '#';
                tmp += (a[i] + '0');
            }
            m[tmp].push_back(s);
        }
        for(auto& n:m)  res.push_back(n.second);
        return res;
    }
};

这里有个小技巧，为了避免对字母数组进行子遍历比较每个字母出现情况，我们可以将字母的出现情况以字符串的形式保存下来，并将这个字符串作为哈希表的键值，这样可以大大减少耗费时间。
我这里用的标识方式是'#0#0#0...#0'，相邻两个字母出现次数用#隔开。

方法三

这种方法比较难想到，需要一定的数理知识。

算术基本定理，又称为正整数的唯一分解定理，即：每个大于1的自然数，要么本身就是质数，要么可以写为2个以上的质数的积，而且这些质因子按大小排列之后，写法仅有一种方式。

因此利用这个我们将每个字符映射到相应的质数，一个字符串则就对应于一个独一无二的质数的乘积，将这个乘积作为哈希表的键值

代码

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map<long, vector<string>> m;
        vector<int> prime = {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};
        for(auto s:strs){
            long k = 1;
            for(auto c:s){
                k *= prime[c-'a'];
            }
            m[k].push_back(s);
        }
        for(auto& n:m)  res.push_back(n.second);
        return res;
    }
};