Leetcode 每日一题6 Group Anagrams

题意

给一个数组，起元素为只包含英文小写字母的单词。

要求分组输出使用了相同字符构造的单词，比如tea和eat就是同类单词。

思路

将所有的单词遍历一遍，将同类单词放到同一个位置中去，关键是这个映射要怎么实现。对于一个长度为m的单词，我们可以用O(m)的时间遍历出各字符的使用次数。接着，我们将其转化成字符串，对于某个字符，其出现次数可以编码成cnt + char，然后按照英文字母表顺序连接起来。比如，teaa编码成2a1e1t。

上面的编码使用了一个优化，即对于出现次数的0的字母，不编码到字符串中。

假如追求极致，还可以对编码继续优化。

• 对于出现次数为1的字母，可以不写上cnt。比如teaa可以写成2aet。
• 当cnt很大时，可以使用整形来表示。比如250，使用char来表示需要3个字节，使用整形只要1个字节。

编码是个很有趣的知识点，上面的编码方式似乎都有专门的名称，以后有空的话专门写篇博客总结一下，这里留个坑:)

代码

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> v;
        unordered_map<string, vector<string>> m;
        for (auto i: strs) {
            m[hashWord(i)].push_back(i);
        }
        for (auto it: m) {
            v.push_back(it.second);
        }
        return v;
    }
    string hashWord(string s) {
        vector<int> cnt(26, 0);
        for (int i = 0; i < s.length(); i++) {
            cnt[s[i] - 'a']++;
        }
        
        string hash;
        for (int i = 0; i < 26; i++) {
            if (!cnt[i])
                continue;
            hash += string(cnt[i], 'a' + i);
        }
        return hash;
    }
};