哈希算法题目：字母异位词分组

题目描述
给定一个字符串数组 strs，请你将字母异位词组合在一起。字母异位词指的是字母相同，但排列不同的字符串。例如，"eat"、"tea"、"ate" 互为字母异位词。最终结果可以以任意顺序输出。

示例
输入：strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出：[["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]

解题思路

1. 核心问题：如何判断两个字符串是字母异位词？

   • 异位词的字符种类和数量完全相同，仅顺序不同。
   • 若直接比较每个字符串的字符频率，时间复杂度较高。

2. 哈希表的关键作用：

   • 将每个字符串映射到同一个键（Key），使得所有异位词的键相同。
   • 哈希表的键可以是：
     • 排序后的字符串（异位词排序后结果相同）。
     • 字符计数数组（转换为唯一标识，如 #1#0#0...#2 形式）。

3. 步骤：

   • 遍历每个字符串，计算其对应的键。
   • 将字符串加入哈希表中键对应的列表。
   • 最终返回哈希表的所有值。

详细解题过程

步骤 1：选择键的生成方式

• 方法 1：排序字符串

  • 对每个字符串按字母排序（如 "tea" → "aet"）。
  • 异位词排序后结果相同，可直接作为键。
  • 时间复杂度：排序每个字符串需 O(K log K)，其中 K 为字符串最大长度。

• 方法 2：字符计数编码

  • 统计每个字符串中字符的频率（例如 a:1, e:1, t:1）。
  • 将频率数组转换为唯一字符串（如 #1#1#1#0...），避免排序开销。
  • 时间复杂度：O(K)，适合字符串较长但字符集有限的情况（如仅小写字母）。

本例中字符串仅包含小写字母，我们选择字符计数编码以提高效率。

步骤 2：实现字符计数编码

• 创建长度为 26 的数组，记录每个字符的出现次数。
• 遍历字符串的每个字符，计算 char - 'a' 得到索引，增加对应位置的计数。
• 将计数数组转换为唯一键：例如，[1,0,0,...,2] 转换为 "1#0#0...#2"（用 # 分隔避免冲突）。

举例：

• "eat" → 计数数组 [a:1, e:1, t:1] → 键 "1#1#1#0#0...#0"（共 26 位）。
• "tea" → 相同计数数组 → 相同键。

步骤 3：构建哈希表分组

• 初始化哈希表 map，键为计数编码字符串，值为原始字符串列表。
• 遍历 strs 中的每个字符串：
  1. 计算其计数编码键。
  2. 若键不存在于 map，新建空列表。
  3. 将当前字符串加入该键对应的列表。
• 最终返回 map 中所有值的集合。

代码实现（伪代码）

def groupAnagrams(strs):
    map = {}
    for s in strs:
        count = [0] * 26  # 26个小写字母的计数数组
        for char in s:
            count[ord(char) - ord('a')] += 1
        key = '#'.join(str(x) for x in count)  # 转换为唯一字符串键
        if key not in map:
            map[key] = []
        map[key].append(s)
    return list(map.values())

复杂度分析

• 时间复杂度：O(N * K)，其中 N 是字符串数量，K 是字符串最大长度。
• 空间复杂度：O(N * K)，哈希表存储所有字符串的键和值。

关键总结

• 利用哈希表将异位词映射到同一键是核心技巧。
• 键的生成方式可根据数据特点优化（排序适用于短字符串，计数编码适用于长字符串）。
• 此题是哈希表用于“分组”问题的经典场景，强调了键的设计如何简化复杂逻辑。