变位词组-哈希表

孙泽辉

发布于：2021年8月7日

字数：330字

时长：1分钟

次浏览

好巧妙的算法！

面试题 10.02. 变位词组

难度 中等

编写一种方法，对字符串数组进行排序，将所有变位词组合在一起。变位词是指字母相同，但排列不同的字符串。

**注意：**本题相对原题稍作修改

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

说明：

• 所有输入均为小写字母。
• 不考虑答案输出的顺序。

题解

function groupAnagrams(strs: string[]): string[][] {
  const hashmap = new Map();
  for (const s of strs) {
    const charNums = new Array<number>(26).fill(0);
    // 统计s的每个字符有多少
    for (const c of s) {
      charNums[c.charCodeAt(0) - 97]++;
    }
      
    // 记录到hashmap
    let t = new String();
    for (let i = 0; i < charNums.length; i++) {
      const element = charNums[i];
      t += element + charNums[i].toString();
    }
    const values: Array<string> = hashmap.get(t) || [];
    values.push(s);
    hashmap.set(t, values);
  }
  return [...hashmap.values()];
}

console.log(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]));

/*
output:
[ [ 'eat', 'tea', 'ate' ], [ 'tan', 'nat' ], [ 'bat' ] ]

*/

思路就是根据字符出现的数量分类，把每个类型都堆到哈希表里，就自动分类了，就把values返回就可以了

哔哩哔哩：

• 《程序员面试金典》10.02. 变位词组 Group Anagrams LCCI 【LeetCode 力扣官方题解】_哔哩哔哩_bilibili