字母异位词分组
字数 2421 2025-12-14 23:00:28

字母异位词分组

题目描述

给你一个字符串数组 strs，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

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

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

解题过程

步骤 1：理解核心问题
字母异位词的定义是关键：两个字符串互为字母异位词，当且仅当它们包含的字母种类和每个字母的数量完全一致，仅仅是排列顺序不同。例如，“eat“、”tea“、”ate“是字母异位词，因为它们都包含1个e、1个a、1个t。

目标：将所有互为字母异位词的字符串分到同一个组中。

步骤 2：寻找分组依据（哈希的“键”）
我们需要找到一个“签名”或“特征”，这个特征对于同一组字母异位词是唯一且相同的，对于不同组的字母异位词是不同的。这样我们就可以用这个特征作为哈希表的键（Key），将原字符串作为该键对应的值列表（Value）中的元素。

如何计算这个特征？

方案 1：排序字符串

  • 思路：既然字母异位词排序后结果相同，可以将排序后的字符串作为“键”。
  • 操作：对每个字符串s，将其字符排序得到s_sorted。例如：
    • "eat" -> 排序 -> "aet"
    • "tea" -> 排序 -> "aet"
  • 那么"aet"就成为了["eat", "tea"]这一组的键。
  • 时间复杂度：排序每个字符串，假设字符串最大长度为K，排序一个字符串的时间复杂度是O(K log K)。对于N个字符串，总时间复杂度为O(N * K log K)。

方案 2：计数编码

  • 思路：统计每个字符串中26个字母出现的次数，然后将统计结果编码成一个唯一的字符串（例如，用#分隔计数）作为键。
  • 操作：创建一个长度为26的数组count，记录每个字母出现的次数。然后生成一个如"#1#0#0...#1#0#0"的字符串（其中数字代表该位置字母出现的次数）。
  • 例如："eat"的计数是[a:1, e:1, t:1]，编码为"#1#1#0#0...#1..."（位置对应a, e, t...）。
  • 时间复杂度：需要遍历每个字符串的每个字符来计数，O(N * K)，然后将计数数组编码为字符串（固定26次操作），总时间复杂度为O(N * K)。当K较大时，此方法可能比排序法更优。

步骤 3：选择哈希表结构
我们使用一个哈希表（字典/映射），其结构为：Map<Key, List<String>>。

  • Key：我们计算出的特征（排序后的字符串 或 计数编码字符串）。
  • Value：一个列表，用于存放所有具有相同Key的原字符串。

步骤 4：详细步骤（以排序法为例）

  1. 初始化一个空的哈希表 Map<String, List<String>> map = new HashMap<>();。
  2. 遍历输入字符串数组 strs 中的每个字符串 s：
    a. 将当前字符串 s 转换为字符数组：char[] chars = s.toCharArray();
    b. 对字符数组进行排序：Arrays.sort(chars);
    c. 将排序后的字符数组转换回字符串，作为键：String key = new String(chars);
    d. 在哈希表 map 中查找这个 key：
    • 如果 map 中不存在这个 key，则创建一个新的空列表，并将 (key, 新列表) 存入 map。
    • 从 map 中获取这个 key 对应的列表 list。
      e. 将原始字符串 s 添加到这个列表 list 中。
  3. 遍历结束后，map 中的所有值（即那些列表）就是我们需要的结果分组。
  4. 将 map 中的所有值收集到一个新的列表 List<List<String>> result 中并返回。

步骤 5：举例说明
输入：strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
过程：

  • 处理 "eat"：排序后键为 "aet"，map 中加入 "aet" -> ["eat"]。
  • 处理 "tea"：排序后键为 "aet"，找到已有列表，加入，变为 "aet" -> ["eat", "tea"]。
  • 处理 "tan"：排序后键为 "ant"，map 中加入 "ant" -> ["tan"]。
  • 处理 "ate"：排序后键为 "aet"，加入列表，变为 "aet" -> ["eat", "tea", "ate"]。
  • 处理 "nat"：排序后键为 "ant"，加入列表，变为 "ant" -> ["tan", "nat"]。
  • 处理 "bat"：排序后键为 "abt"，map 中加入 "abt" -> ["bat"]。

最终结果：map 的值列表为 [["eat","tea","ate"], ["tan","nat"], ["bat"]]，顺序不限。

步骤 6：复杂度分析

  • 时间复杂度：O(N * K log K)，其中 N 是 strs 的长度，K 是 strs 中字符串的最大长度。主要开销在于对每个字符串排序。
  • 空间复杂度：O(N * K)，哈希表需要存储所有字符串（原始字符串和键，但键的总长度不超过所有字符串的总长度）。

步骤 7：关键点总结

  • 哈希思想：将看似复杂的“异位词”判定问题，转化为一个寻找“唯一、稳定特征”的问题，利用哈希表进行高效分组。
  • 键的设计：排序字符串是最直观的键；计数编码是另一种高效的键生成方式，尤其在字符串较长时可能更有优势。
  • 映射结构：哈希表的值是一个列表，用于动态收集同一组的元素。
字母异位词分组 题目描述 给你一个字符串数组 strs ，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 示例 1: 示例 2: 示例 3: 解题过程 步骤 1：理解核心问题 字母异位词的定义是关键：两个字符串互为字母异位词，当且仅当它们包含的字母种类和每个字母的数量完全一致，仅仅是排列顺序不同。例如，“eat“、”tea“、”ate“是字母异位词，因为它们都包含1个 e 、1个 a 、1个 t 。 目标 ：将所有互为字母异位词的字符串分到同一个组中。 步骤 2：寻找分组依据（哈希的“键”） 我们需要找到一个“签名”或“特征”，这个特征对于同一组字母异位词是 唯一且相同 的，对于不同组的字母异位词是 不同 的。这样我们就可以用这个特征作为哈希表的键（Key），将原字符串作为该键对应的值列表（Value）中的元素。 如何计算这个特征？ 方案 1：排序字符串 思路：既然字母异位词排序后结果相同，可以将排序后的字符串作为“键”。 操作：对每个字符串 s ，将其字符排序得到 s_sorted 。例如： "eat" -> 排序 -> "aet" "tea" -> 排序 -> "aet" 那么 "aet" 就成为了 ["eat", "tea"] 这一组的键。 时间复杂度：排序每个字符串，假设字符串最大长度为 K ，排序一个字符串的时间复杂度是 O(K log K) 。对于 N 个字符串，总时间复杂度为 O(N * K log K) 。 方案 2：计数编码 思路：统计每个字符串中26个字母出现的次数，然后将统计结果编码成一个唯一的字符串（例如，用 # 分隔计数）作为键。 操作：创建一个长度为26的数组 count ，记录每个字母出现的次数。然后生成一个如 "#1#0#0...#1#0#0" 的字符串（其中数字代表该位置字母出现的次数）。 例如： "eat" 的计数是 [a:1, e:1, t:1] ，编码为 "#1#1#0#0...#1..." （位置对应a, e, t...）。 时间复杂度：需要遍历每个字符串的每个字符来计数， O(N * K) ，然后将计数数组编码为字符串（固定26次操作），总时间复杂度为 O(N * K) 。当 K 较大时，此方法可能比排序法更优。 步骤 3：选择哈希表结构 我们使用一个哈希表（字典/映射），其结构为： Map<Key, List<String>> 。 Key ：我们计算出的特征（排序后的字符串 或 计数编码字符串）。 Value ：一个列表，用于存放所有具有相同 Key 的原字符串。 步骤 4：详细步骤（以排序法为例） 初始化一个空的哈希表 Map<String, List<String>> map = new HashMap<>(); 。 遍历输入字符串数组 strs 中的每个字符串 s ： a. 将当前字符串 s 转换为字符数组： char[] chars = s.toCharArray(); b. 对字符数组进行排序： Arrays.sort(chars); c. 将排序后的字符数组转换回字符串，作为键： String key = new String(chars); d. 在哈希表 map 中查找这个 key ： 如果 map 中不存在这个 key ，则创建一个新的空列表，并将 (key, 新列表) 存入 map 。 从 map 中获取这个 key 对应的列表 list 。 e. 将原始字符串 s 添加到这个列表 list 中。 遍历结束后， map 中的所有值（即那些列表）就是我们需要的结果分组。 将 map 中的所有值收集到一个新的列表 List<List<String>> result 中并返回。 步骤 5：举例说明 输入： strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 过程： 处理 "eat" ：排序后键为 "aet" ， map 中加入 "aet" -> ["eat"] 。 处理 "tea" ：排序后键为 "aet" ，找到已有列表，加入，变为 "aet" -> ["eat", "tea"] 。 处理 "tan" ：排序后键为 "ant" ， map 中加入 "ant" -> ["tan"] 。 处理 "ate" ：排序后键为 "aet" ，加入列表，变为 "aet" -> ["eat", "tea", "ate"] 。 处理 "nat" ：排序后键为 "ant" ，加入列表，变为 "ant" -> ["tan", "nat"] 。 处理 "bat" ：排序后键为 "abt" ， map 中加入 "abt" -> ["bat"] 。 最终结果： map 的值列表为 [["eat","tea","ate"], ["tan","nat"], ["bat"]] ，顺序不限。 步骤 6：复杂度分析 时间复杂度： O(N * K log K) ，其中 N 是 strs 的长度， K 是 strs 中字符串的最大长度。主要开销在于对每个字符串排序。 空间复杂度： O(N * K) ，哈希表需要存储所有字符串（原始字符串和键，但键的总长度不超过所有字符串的总长度）。 步骤 7：关键点总结 哈希思想 ：将看似复杂的“异位词”判定问题，转化为一个寻找“唯一、稳定特征”的问题，利用哈希表进行高效分组。 键的设计 ：排序字符串是最直观的键；计数编码是另一种高效的键生成方式，尤其在字符串较长时可能更有优势。 映射结构 ：哈希表的值是一个列表，用于动态收集同一组的元素。