原题：字母异位词分组

思路：字符串中字符的种类和出现次数相同，基于这个规律做哈希

思路

  1. 每个字符串中字符的种类和出现次数必定相同，要基于此求出哈希值 hashCode

  2. 判断哈希表上是否有值 hashMap.has(hashCode)，没有就新建数组放在哈希表上，同时推入到结果数组中，有则直接往其中推入当前字符串 hashMap.get(hashCode).push(str)

1. 初始化

1
2
3
4
5
6
// 结果数组
const result = [];
// 哈希表
const hashMap = new Map();
// 记录 'a' 的 ASCII 码，方便后续计算字母出现次数
const aCode = 'a'.charCodeAt(0);

1. 求字符串对应哈希值

循环字符串列表，对每个字符串求哈希值

题目中提示只会有小写字母，所以我们申请一个长度 26 的数组，用于计算每个字母的出现次数，并且把其值初始化为 0

1
2
3
4
const counter = new Array(26);
for (let j = 0; j < counter.length; j++) {
  counter[j] = 0;
}

遍历当前字符串的每一个字符，将其 ASCII 码减去 'a' 的 ASCII 码的下标的计数器上计数

1
2
3
4
5
// 遍历每一个字符
for (let j = 0; j < strLen; j++) {
  // 'a' 的值派上用场了，从下标 0 开始从 'a' ~ 'z'，对应字符增加计数
  counter[str.charCodeAt(j) - aCode]++;
}

使用计数器计算哈希值，按照 ${字母}${出现次数}... 的规则拼接，0 次的不处理

1
2
3
4
5
6
7
8
9
10
// 存放拼接的哈希值
let hashCode = '';
// 遍历计数器
for (let j = 0; j < 26; j++) {
  // 如果 ＞ 0，拼接哈希值，例如 moon -> 'm1n1o2'
  if (counter[j]) {
    // 'a' 的值加上下标就是对应字母的值，转换成字符串，和出现次数拼接
    hashCode += String.fromCharCode(aCode + j) + counter[j];
  }
}

2. 哈希表处理

如果哈希表上哈希值的位置已有数组，直接把当前字符推入，否则在该位置上新建数组，同时把该数组推入结果

1
2
3
4
5
6
7
8
// 如果哈希值上已经存在数组，推入
if (hashMap.has(hashCode)) hashMap.get(hashCode).push(str);
// 没有则新建数组
else {
  const arr = [str];
  result.push(arr);
  hashMap.set(hashCode, arr);
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * 思路：
 * 字符的类型和出现次数肯定是一样的
 * 由此可以把字符计数来当成哈希值
 * 哈希值一致的字符串为一组
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
  // 结果数组
  const result = [];
  // 哈希表
  const hashMap = new Map();
  // 记录 'a' 的 ASCII 码，方便后续使用
  const aCode = 'a'.charCodeAt(0);
  // 遍历每一个字符串
  for (let i = 0; i < strs.length; i++) {
    const str = strs[i];
    const strLen = str.length;
    // 计数器，用于记录每个字符的出现次数，因为只有小写字母，只申请 26 长度
    const counter = new Array(26);
    for (let j = 0; j < counter.length; j++) {
      counter[j] = 0;
    }
    // 遍历每一个字符
    for (let j = 0; j < strLen; j++) {
      // 'a' 的值派上用场了，从下标 0 开始从 'a' ~ 'z'，对应字符增加计数
      counter[str.charCodeAt(j) - aCode]++;
    }
    // 存放拼接的哈希值
    let hashCode = '';
    // 遍历计数器
    for (let j = 0; j < 26; j++) {
      // 如果 ＞ 0，拼接哈希值，例如 moon -> 'm1n1o2'
      if (counter[j]) {
        // 'a' 的值加上下标就是对应字母的值，转换成字符串，和出现次数拼接
        hashCode += String.fromCharCode(aCode + j) + counter[j];
      }
    }
    // 如果哈希值上已经存在数组，推入
    if (hashMap.has(hashCode)) hashMap.get(hashCode).push(str);
    // 没有则新建数组
    else {
      const arr = [str];
      result.push(arr);
      hashMap.set(hashCode, arr);
    }
  }
  return result;
};