49. 字母异位词分组

Origin: LeetCode 49

题目描述

给定一个字符串数组，将字母异位词分组。字母异位词指字母相同但排列不同的字符串。

示例

Input: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Explanation:

• “eat”、“tea”、“ate” 是一组
• “tan”、“nat” 是一组
• “bat” 单独一组

约束

• 1 <= strs.length <= 10
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

关键信息

• 异位词 = 字母相同排列不同
• 分组 = 找共同 key
• key 可以是排序后的字符串，也可以是字母频次

Resolution

我的解法

function groupAnagrams(strs: string[]): string[][] {
    const strMap = new Map()
    for (let i = 0; i < strs.length; i++) {
        let cur = strs[i]
        let sortedCur = cur.split('').sort().join('')
        if (strMap.has(sortedCur)) {
            strMap.set(sortedCur, [...strMap.get(sortedCur), cur])
        } else {
            strMap.set(sortedCur, [cur])
        }
    }
    return Array.from(strMap.values())
}

解题思路

排序后的字符串作为 Map key，异位词排序后相同，自然分到一组。

• 每个字符串 split → sort → join 得到 key
• Map<key, string[]> 分组
• 最后返回 Map.values()

复杂度

• 时间：O(n × k log k)，n 是字符串个数，k 是最长字符串长度（排序）
• 空间：O(n × k)，Map 存储