力扣第四十九题——字母异位词分组

内容介绍

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

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

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

完整代码

 class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

思路详解

一、问题分析

字母异位词指的是由相同字母组成的字符串，但字母的顺序可能不同。例如，“eat” 和 “ate” 就是字母异位词。给定一个字符串数组，要求将这些字符串按照字母异位词进行分组。

二、解题思路

1. 使用哈希表（Map）来存储分组结果。键（Key）为排序后的字符串，值（Value）为字母异位词组成的列表。

2. 遍历字符串数组，对每个字符串进行以下操作：

   a. 将字符串转换为字符数组。

   b. 对字符数组进行排序。

   c. 将排序后的字符数组转换为字符串，作为哈希表的键。

3. 判断哈希表中是否已存在该键，如果存在，则将当前字符串添加到对应的列表中；如果不存在，则创建一个新的列表，并将当前字符串添加到列表中。

4. 将键值对存入哈希表。

5. 遍历结束后，将哈希表的值转换为列表，并返回结果。

三、代码详解

1. 定义一个Solution类，并创建一个groupAnagrams方法，接收一个字符串数组作为参数。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // ...
    }
}

1. 创建一个HashMap，用于存储分组结果。

Map<String, List<String>> map = new HashMap<String, List<String>>();

1. 遍历字符串数组。

for (String str : strs) {
    // ...
}

1. 将字符串转换为字符数组，并对其进行排序。

char[] array = str.toCharArray();
Arrays.sort(array);

1. 将排序后的字符数组转换为字符串，作为哈希表的键。

String key = new String(array);

1. 判断哈希表中是否已存在该键，如果存在，则将当前字符串添加到对应的列表中；如果不存在，则创建一个新的列表。

List<String> list = map.getOrDefault(key, new ArrayList<String>());
list.add(str);

1. 将键值对存入哈希表。

map.put(key, list);

1. 遍历结束后，将哈希表的值转换为列表，并返回结果。

return new ArrayList<List<String>>(map.values());

四、总结

通过以上步骤，我们可以将字符串数组中的字母异位词进行分组，并返回分组结果。该算法的时间复杂度为O(n * klogk)，其中n为字符串数组的长度，k为字符串的最大长度。排序操作是算法中的主要耗时部分，但整体性能仍然较为优秀。

知识点精炼

一、核心概念

1. 字母异位词：由相同字母组成的字符串，但字母顺序不同。
2. 哈希表（HashMap）：一种基于键值对的数据结构，用于存储和查找数据。

二、知识点精炼

1. 哈希表的应用

   • 键（Key）：排序后的字符串，用于标识一组字母异位词。
   • 值（Value）：字符串列表，存储具有相同字母异位词的字符串。

2. 字符数组排序

   • 使用Arrays.sort()方法对字符数组进行排序，以便生成哈希表的键。

3. 哈希表操作

   • getOrDefault()：获取指定键对应的值，如果键不存在，则返回默认值。
   • put()：将键值对存入哈希表。

4. 遍历与返回结果

   • 遍历字符串数组，将每个字符串分组到对应的字母异位词列表。
   • 将哈希表的值转换为列表，并返回分组结果。

三、性能分析

1. 时间复杂度：O(n * klogk)，其中n为字符串数组的长度，k为字符串的最大长度。
2. 空间复杂度：O(n * k)，用于存储哈希表及分组结果。

四、拓展与应用

1. 字符串处理：掌握字符数组的排序、转换等操作。
2. 哈希表应用：熟练运用哈希表进行数据分组、查找等操作。
3. 实际场景：该算法可应用于文本分析、字符串检索等场景，提高数据处理效率。

 哈希表的详细介绍

哈希表（HashMap）是一种非常强大的数据结构，它在很多算法问题中都有广泛的应用。以下是关于哈希表在分组字母异位词问题中的详细应用解释：

哈希表的基本概念

哈希表是一种基于键值对（Key-Value Pair）的抽象数据类型，它通过一个哈希函数来计算键的哈希值，并将这个值映射到表中的一个位置来存储对应的值。这种数据结构提供了非常快速的插入和查找操作。

哈希表在分组字母异位词中的应用

1. 键（Key）的选择：

   • 在分组字母异位词的问题中，我们需要一个能够唯一标识一组字母异位词的键。
   • 我们通过对字符串中的字符进行排序来生成这个键。排序后的字符串对于同一组字母异位词是相同的，因此可以作为哈希表的键。
   • 例如，字符串 “eat” 和 “ate” 经过排序后都变成 “aet”，因此它们可以共享同一个键。

2. 值（Value）的存储：

   • 哈希表的值是一个列表（List），用于存储所有具有相同键的原始字符串。
   • 当我们遇到一个新的字符串时，我们首先将其排序，然后检查排序后的字符串是否已经作为键存在于哈希表中。
   • 如果存在，我们将原始字符串添加到对应键的列表中；如果不存在，我们创建一个新的列表并添加字符串，然后将这个列表与排序后的字符串作为键值对存入哈希表。

3. 哈希表的查找与插入操作：

   • getOrDefault(key, defaultValue) 方法用于查找哈希表中是否已存在特定的键。如果键存在，它返回与键关联的值；如果不存在，它返回一个默认值（在这个问题中是一个新的列表）。
   • put(key, value) 方法用于将一个新的键值对插入哈希表，或者更新哈希表中已存在的键的值。

代码示例

以下是哈希表在分组字母异位词问题中的具体应用代码：

Map<String, List<String>> map = new HashMap<>();

for (String str : strs) {
    // 将字符串转换为字符数组并排序
    char[] array = str.toCharArray();
    Arrays.sort(array);
    // 将排序后的字符数组转换回字符串，作为哈希表的键
    String key = new String(array);
    
    // 使用 getOrDefault 查找哈希表中是否已存在该键
    // 如果不存在，则返回一个新的空列表
    List<String> list = map.getOrDefault(key, new ArrayList<>());
    
    // 将原始字符串添加到列表中
    list.add(str);
    
    // 将更新后的列表存回哈希表
    map.put(key, list);
}

// 返回哈希表中所有的值，这些值就是分组后的字母异位词列表
return new ArrayList<>(map.values());

通过这种方式，哈希表帮助我们以高效的方式完成了字母异位词的分组。每个字符串只需要一次排序操作，而查找和插入操作的平均时间复杂度为 O(1)，这使得整体算法效率非常高。