Java的Map、HashMap、ArrayList集合实例使用，力扣(LeetCode)刷题第49题：字母异位词分组_leetcode49题java

---

前言

[题目地址：字母异位词分组]

一、题目介绍

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

示例 1:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]
1
2
3
4
5
6
7

二、解题思路

1.分析题目

一开始想到了一点思路，但是不知道如何下手，于是去看了官方的解答，确实很不错，十分的巧妙，而且把哈希的思想使用的非常好，也帮助自己巩固了一下Java中这些集合的使用方法。

2.官方思路

两个字符串互为字母异位词，当且仅当两个字符串包含的字母相同。同一组字母异位词中的字符串具备相同点，可以使用相同点作为一组字母异位词的标志，使用哈希表存储每一组字母异位词，哈希表的键为一组字母异位词的标志，哈希表的值为一组字母异位词列表。

遍历每个字符串，对于每个字符串，得到该字符串所在的一组字母异位词的标志，将当前字符串加入该组字母异位词的列表中。遍历全部字符串之后，哈希表中的每个键值对即为一组字母异位词。

以下的两种方法分别使用排序和计数作为哈希表的键。

3.代码

1.方法一：排序

Java代码详细注释

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {//增强for遍历每一个字符串
            char[] array = str.toCharArray();//将此字符串转换为新的字符数组,便于排序
            Arrays.sort(array);//对字符数组排序 
            String key = new String(array);//将字符数组变为String类型的ksy
            List<String> list = map.getOrDefault(key, new ArrayList<String>());//返回到指定键所映射的值，或 defaultValue如果此映射包含该键的映射。
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());//构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序。
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

复杂度分析

• 时间复杂度：O(nklogk)，其中 n 是strs 中的字符串的数量，kk是strs 中的字符串的的最大长度。需要遍历 n个字符串，对于每个字符串，需要 O(klogk) 的时间进行排序以及O(1) 的时间更新哈希表，因此总时间复杂度是 O(nk logk)。
• 空间复杂度：O(nk)，其中 n是strs 中的字符串的数量，k 是strs 中的字符串的的最大长度。需要用哈希表存储全部字符串。

这里用到了很多Java的集合，如果大家对于这块不熟悉，可以借助官方的api搜索学习，看的多了自然也就记住了。 有需要官方api的可以评论区留言！

2.方法二：计数

Java代码详细注释

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            int[] counts = new int[26];
            int length = str.length();
            for (int i = 0; i < length; i++) {
                counts[str.charAt(i) - 'a']++; //返回 char指定索引处的值。 也就是对字符进行计数
            }
            // 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < 26; i++) {
                if (counts[i] != 0) {
                    sb.append((char) ('a' + i));
                    sb.append(counts[i]);
                }
            }
            String key = sb.toString();
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}
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

感觉计数比上面繁琐多了，害！

三、总结

从编程中学习思想和思路，还能巩固学习的其他知识，何乐而不为呢？

记录时间：2020年12月14日