Hi 大家好，我是张小猪。欢迎来到『宝宝也能看懂』系列特别篇 - 30-Day LeetCoding Challenge。
这是一个 leetcode 官方的小活动。可以在官网看到，从 4 月 1 号开始，每天官方会选出一道题，在 24 小时内完成即可获得一点小奖励。虽然奖励似乎也没什么用，不过作为一个官方的打卡活动，小猪还是来打一下卡吧，正好作为每天下班回家后的娱乐。
这里是 4 月 6 号的题，也是题目列表中的第 49 题 -- 『字母异位词分组』
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]说明：
- 所有输入均为小写字母。
- 不考虑答案输出的顺序。
MEDIUM
由于题目不限制返回数据的顺序，所以我们只需要做字符串内容的区分即可。而这个区分，笼统的来说，就是找到一个格式化或者是序列化的方式，这个方式只关心不同字母出现的次数，并不关心它们的位置。
基于上面的思路，我们可以轻松的想到一个最基础的方式，即统计单词中字母出现的频次。这种方式实现起来非常轻松，但是性能实在是不敢恭维。
在遍历每一个单词的时候，我们可以统计其中不同字母出现的次数，并将统计结果做互相比较，从而做到将不同类型的单词归类输出。具体代码如下：
const wordHash = word => {
const map = new Map();
for (let i = 0; i < word.length; ++i) {
const char = word[i];
map.set(char, map.has(char) ? map.get(char) + 1 : 1);
}
return map;
};
const compareHash = (map1, map2) => {
if (map1.size !== map2.size) return false;
for (let [char, count] of map1.entries()) {
if (!map2.has(char) || map2.get(char) !== count) return false;
}
return true;
};
const groupAnagrams = strs => {
const ret = [];
const hashMap = new Map();
for (const word of strs) {
const hash = wordHash(word);
let exist = false;
for (let [map, idx] of hashMap.entries()) {
if (!compareHash(hash, map)) continue;
exist = true;
ret[idx].push(word);
break;
}
!exist && hashMap.set(hash, ret.push([word]) - 1);
}
return ret;
};上面思路里，处理过程的逻辑我们是比较难优化的，不过这个序列化的方式我们可以让它变得更快一些。
首先，由于只有小写字母，所以我们可以基于字母顺序对单词内的字符进行排序，这样就可以完成单词的归类啦。具体代码如下：
const groupAnagrams = strs => {
const hashMap = new Map();
for (const word of strs) {
const serializeWord = word.split("").sort().join("");
hashMap.has(serializeWord)
? hashMap.get(serializeWord).push(word)
: hashMap.set(serializeWord, [word]);
}
return [...hashMap.values()];
};再看上面的过程，其中字符串的排序过程还是比较耗时的。所以我们可以尝试再换一下特征提取方式。
我们可以申明一个长度为 26 的数组，基于字母 charCode 为下标来记录每个字母出现的次数，然后把这个数组转换为一个字符串作为序列化的结果。这样即可完成单词的归类啦。具体代码如下：
const groupAnagrams = strs => {
const BASE_CODE = 97;
const hashMap = new Map();
for (const word of strs) {
const countList = new Int8Array(26);
for (let j = 0; j < word.length; ++j) {
++countList[word.charCodeAt(j) - BASE_CODE];
}
const serializeWord = countList.join("");
hashMap.has(serializeWord)
? hashMap.get(serializeWord).push(word)
: hashMap.set(serializeWord, [word]);
}
return [...hashMap.values()];
};在上面的转化过程中，我们还是每次都需要借助额外的数组，以及把数组转化为字符串。这次我们尝试一个单纯的数字计算，从而再优化这部分的性能。
我们可以利用质数的特殊性质来参与计算，从而实现只用一个数字就能完成特征标识的任务。不过这里有一个前提，即计算的结果不会超出数字的表示范围。具体代码如下：
const groupAnagrams = strs => {
const BASE_CODE = 97;
const CHAR_VAL_MAP = [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];
const hashMap = new Map();
for (const word of strs) {
let val = 1;
for (let j = 0; j < word.length; ++j) {
val *= CHAR_VAL_MAP[word.charCodeAt(j) - BASE_CODE];
}
hashMap.has(val)
? hashMap.get(val).push(word)
: hashMap.set(val, [word]);
}
return [...hashMap.values()];
};终于出现不是 EASY 难度的题了，可喜可贺！
这道题的核心逻辑并不复杂，很容易 AC，只是在具体的序列化部分我们可以有一些优化空间，从而提升性能。小猪给出了我自己的优化思路，希望能帮到有需要的小伙伴。
如果觉得不错的话，记得『三连』哦。小猪爱你们哟~
