[!info] related notes 对单词中的字母种类和个数进行摘要的方法

字母异位词分组

分析

![[字母异位词分组分析.excalidraw]]

难点

大体思路正确，但是哈希表的处理存在问题。 想的是使用多个哈希表 来存储每个单词的 字母 统计情况，然后再用什么方法来 对每个 哈希表进行 摘要，相等的放一起。

应该直接用 摘要方法 来对每个数据进行摘要，然后 把 摘要信息 作为 哈希表 的 key，单词组合成数组 放入 value 中。

解法

字符计数法 (O(N × K))

function groupAnagrams(strs: string[]): string[][] {
    const map = new Map<string, string[]>();

    for (const str of strs) {
        // digest 方法 见 [对单词中的字母种类和个数进行摘要的方法](对单词中的字母种类和个数进行摘要的方法)
        const key = digestWithConstructedHash(str);

        if (!map.has(key)) {
            map.set(key, []);
        }
        map.get(key)!.push(str);
    }

    return Array.from(map.values());
}

排序法 (O(N × K log K))

替换上面的 的 digestWithConstructedHash 为 digestBySort