/*
* @lc app=leetcode id=49 lang=javascript
*
* [49] Group Anagrams
*/
/**
* @param {string[]} strs
* @return {string[][]}
*/
var groupAnagrams = function (strs) {
// 类似桶排序
let counts = [];
const hashTable = {};
for (let i = 0; i < strs.length; i++) {
const str = strs[i];
counts = Array(26).fill(0);
for (let j = 0; j < str.length; j++) {
counts[str[j].charCodeAt(0) - "a".charCodeAt(0)]++;
}
const key = counts.join("-");
if (!hashTable[key]) {
hashTable[key] = [str];
} else {
hashTable[key].push(str);
}
}
return Object.values(hashTable);
};
Python3 Code:
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
"""
思路同上，在Python中，这里涉及到3个知识点：
1. 使用内置的 defaultdict 字典设置默认值；
2. 内置的 ord 函数，计算ASCII值（等于chr）或Unicode值(等于unichr)；
3. 列表不可哈希，不能作为字典的键，因此这里转为元组；
"""
str_dict = collections.defaultdict(list)
for s in strs:
s_key = [0] * 26
for c in s:
s_key[ord(c)-ord('a')] += 1
str_dict[tuple(s_key)].append(s)
return list(str_dict.values())
CPP Code:
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& A) {
unordered_map<string, int> m;
vector<vector<string>> ans;
for (auto &s : A) {
auto p = s;
sort(p.begin(), p.end());
if (!m.count(p)) {
m[p] = ans.size();
ans.push_back({});
}
ans[m[p]].push_back(s);
}
return ans;
}
};
