当前位置：首页 > news >正文

LeetCode题练习与总结：字母异位词分组

news 来源：原创 2024/5/17 5:54:39

一、题目描述

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

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

二、解题思路

理解问题：我们需要将一组字符串按照字母异位词进行分组。字母异位词指的是字母的排列不同，但是字母的种类和数量完全相同。
创建映射：我们可以使用一个Map来存储每个字符串与其对应的异位词列表。Map的键是一个字符串，表示一个字符串数组，这个数组中的每个元素都是原字符串的一个异位词。Map的值是一个List，存储所有异位词。
处理字符串：对于输入数组中的每个字符串，我们需要进行排序，以便将相同的字母异位词放在一起。例如，"eat"、"tea"和"ate"排序后都变成"aet"。
填充映射：将排序后的字符串作为Map的键，将原始字符串添加到对应的List中。
返回结果：最后，我们需要遍历Map的值，将所有的List收集到一个List中，并返回这个List。

三、具体代码

import java.util.*;public class Solution {public List<List<String>> groupAnagrams(String[] strs) {// 创建一个Map来存储排序后的字符串和对应的异位词列表Map<String, List<String>> map = new HashMap<>();// 遍历所有的字符串for (String str : strs) {// 对字符串进行排序，以便将异位词放在一起char[] charArray = str.toCharArray();Arrays.sort(charArray);String sortedStr = new String(charArray);// 将排序后的字符串作为键，原始字符串添加到对应的List中map.computeIfAbsent(sortedStr, k -> new ArrayList<>()).add(str);}// 收集所有的异位词列表List<List<String>> result = new ArrayList<>();result.addAll(map.values());return result;}
}

四、时间复杂度和空间复杂度

1. 时间复杂度

对于每个字符串，我们都需要进行一次排序操作。字符串排序的时间复杂度是 O(n log n)，其中 n 是字符串的长度。由于字符串的最大长度为 100，这个操作对整个算法的影响较小。
我们还需要遍历所有的字符串，这个操作的时间复杂度是 O(m)，其中 m 是字符串数组的长度。
Map 的 computeIfAbsent 方法在大多数情况下是 O(1)，但在最坏情况下（例如当Map的负载因子达到一定阈值时需要扩容）可能会达到 O(n)。
最后，我们将Map中的所有List添加到结果List中，这个操作的时间复杂度是 O(k)，其中 k 是Map中元素的数量。
综上所述，总的时间复杂度是 O(m * n log n + m * n + k)。由于 m 和 n 都可能非常大，我们可以简化为 O(m * n log n)，这是因为排序操作通常比其他操作更耗时。

2. 空间复杂度

Map 存储了每个排序后的字符串及其对应的原始字符串列表。在最坏的情况下，每个字符串都是唯一的异位词，这意味着 Map 中将有 m 个键值对，每个键值对占用 O(n) 的空间来存储原始字符串列表。
结果List 存储了所有的异位词列表，其空间复杂度为 O(k)。
因此，总的空间复杂度是 O(m * n + k)，其中 m 是字符串数组的长度，n 是字符串的平均长度，k 是Map中元素的数量。在最坏的情况下，k 可能等于 m，因此空间复杂度可以简化为 O(m * n)。

五、总结知识点

1. Java集合框架（Collections Framework）:

HashMap: 一个基于键值对的数据结构，允许使用一个对象作为键来存储和检索另一个对象。在这个例子中，HashMap用于存储排序后的字符串作为键，以及对应的原始字符串列表作为值。
ArrayList: 一个动态数组的实现，用于存储有序集合中的元素。在这个例子中，ArrayList用作HashMap的值，来存储具有相同排序字符串的原始字符串列表。

2. 字符串操作: