力扣经典150题第四十二题：字母异位词分组

力扣经典150题第四十二题：字母异位词分组

引言

本篇博客介绍了力扣经典150题中的第四十二题：字母异位词分组。题目要求将给定的字符串数组中的字母异位词分组，并返回分组结果。

题目详解

给定一个字符串数组 strs，将其中字母异位词（由重新排列源单词的所有字母得到的新单词）组合在一起，最终返回分组后的结果列表。
示例 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] 仅包含小写字母

解题思路

要将字母异位词分组，可以使用哈希表进行处理：

1. 创建一个哈希表 map，键为字符串的字符排序后的字符串（作为异位词的标识），值为该异位词所在的分组列表。
2. 遍历字符串数组 strs，对于每个字符串 s：
   • 将 s 转换成字符数组，并进行排序得到新的字符串 sortedStr，作为哈希表的键。
   • 如果 sortedStr 在哈希表中不存在，创建一个新的分组列表，并将当前字符串 s 加入到列表中，同时在哈希表中添加 sortedStr 到对应的分组列表。
   • 如果 sortedStr 在哈希表中存在，直接将当前字符串 s 加入到对应的分组列表中。
3. 最终，遍历哈希表的所有值，将分组列表组成的结果返回。

通过上述步骤，可以将字母异位词分组并返回结果列表。

代码实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class GroupAnagrams {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();

        for (String s : strs) {
            // 将字符串转换成字符数组并排序
            char[] charArray = s.toCharArray();
            Arrays.sort(charArray);
            String sortedStr = new String(charArray);

            // 如果 sortedStr 不在 map 中，创建一个新的分组列表
            if (!map.containsKey(sortedStr)) {
                map.put(sortedStr, new ArrayList<>());
            }
            // 将当前字符串加入到对应的分组列表中
            map.get(sortedStr).add(s);
        }

        // 返回哈希表中的所有分组列表
        return new ArrayList<>(map.values());
    }

    public static void main(String[] args) {
        GroupAnagrams solution = new GroupAnagrams();

        // 示例测试
        String[] strs1 = {"eat", "tea", "tan", "ate", "nat", "bat"};
        System.out.println("输入: " + Arrays.toString(strs1));
        System.out.println("输出: " + solution.groupAnagrams(strs1));

        String[] strs2 = {""};
        System.out.println("输入: " + Arrays.toString(strs2));
        System.out.println("输出: " + solution.groupAnagrams(strs2));

        String[] strs3 = {"a"};
        System.out.println("输入: " + Arrays.toString(strs3));
        System.out.println("输出: " + solution.groupAnagrams(strs3));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

示例演示

展示了几个不同的示例测试，验证了字母异位词分组的功能。

复杂度分析

该解法的时间复杂度为 O(n * k log k)，其中 n 是字符串数组 strs 的长度，k 是字符串的最大长度。空间复杂度为 O(n * k)，主要是哈希表 map 存储的空间。