字母异位词分组
难度:
标签:
题目描述
English description is not available for the problem. Please switch to Chinese.
代码结果
运行时间: 33 ms, 内存: 18.9 MB
/*
* 思路:
* 1. 使用Java Stream API进行流式处理。
* 2. 将字符串数组转为流,映射每个字符串为其排序后的结果,并将其作为键存入Map。
* 3. 将字符串按照键分组后,收集为List。
*/
import java.util.*;
import java.util.stream.Collectors;
public class GroupAnagramsStream {
public List<List<String>> groupAnagrams(String[] strs) {
if (strs == null || strs.length == 0) return new ArrayList<>();
return new ArrayList<>(
Arrays.stream(strs)
.collect(Collectors.groupingBy(
s -> {
char[] chars = s.toCharArray();
Arrays.sort(chars);
return new String(chars);
}
)).values()
);
}
}
解释
方法:
本题解采用了一个哈希表(字典)来组织数据,其中键是字符串排序后的结果,而值是一个列表,包含所有排序后相同的原始字符串。遍历输入数组 `strs`,对于每个字符串,首先将其字符排序,得到一个有序的字符串,然后将原始字符串添加到哈希表的对应列表中。这样,所有变位词都会因为它们排序后的字符串相同而被归到同一个列表中。最后,返回哈希表中所有值构成的列表。
时间复杂度:
O(n * k log k)
空间复杂度:
O(n)
代码细节讲解
🦆
在此题解中,为什么选择使用排序字符串作为哈希表的键而非其他方法如字符计数?
▷🦆
哈希表使用`setdefault`方法来初始化键值对,这与直接检查键是否存在然后再添加有什么不同?哪种方法更高效?
▷🦆
字符串排序和添加到哈希表的过程中,是否存在重复的字符串处理,且如何避免重复处理同一个字符串?
▷