字母异位词分组
难度:
标签:
题目描述
给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 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]
仅包含小写字母
代码结果
运行时间: 68 ms, 内存: 19.8 MB
/*
* 思路:
* 使用Java Streams流式处理,通过对每个字符串进行排序,
* 然后将其收集到Map中,键为排序后的字符串,值为相应的字符串列表。
*/
import java.util.*;
import java.util.stream.Collectors;
public class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
return new ArrayList<>(Arrays.stream(strs)
.collect(Collectors.groupingBy(s -> {
char[] charArray = s.toCharArray();
Arrays.sort(charArray);
return new String(charArray);
})).values());
}
}
解释
方法:
该题解的思路是利用哈希表来将字母异位词分组。具体做法是:遍历字符串数组中的每个字符串,对于每个字符串,统计其中每个字母出现的次数,并将统计结果转换为一个长度为26的元组作为哈希表的键,字符串作为对应键的值。这样,所有字母异位词都会被映射到哈希表中的同一个键上,最后将哈希表中的所有值(即分组后的字母异位词列表)转换为列表返回即可。
时间复杂度:
O(n * k)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么选择使用长度为26的列表来表示每个字符串的字符出现次数,而不是使用哈希表或其他数据结构?
▷🦆
将字符出现次数的列表转换为元组用作哈希键的理由是什么?是否有其他数据结构可以用作哈希键?
▷🦆
在哈希表中,如果两个字符串是字母异位词但顺序不同,它们如何确保映射到同一个键上?
▷🦆
对于空字符串,该算法如何处理?它们在哈希表中的键是什么样的?
▷