JAVA解法
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
// 定义一个储存键值对的 HashMap
Map<String, List<String>> map = new HashMap<String, List<String>>();
// 遍历传进来的字符串数组
for (String str : strs) {
// 每获取一个字符串,将其转换为字符数组
char[] array = str.toCharArray();
// 给字符数组排序
Arrays.sort(array);
// 将排序完的字符数组转换为字符串,并将其作为 map 的键
String key = new String(array);
// 定义一个储存值的 ArrayList<String>,将上一步的键从 map 中查找结果并返回,若不存在,则新建一个键为传进来的 key,值为一个新的 ArrayList<String>
List<String> list = map.getOrDefault(key, new ArrayList<String>());
// 将遍历到的字符串存到 list 中
list.add(str);
// 将储存字母异位词的唯一的 list 与 map 中唯一的 key 进行映射储存
map.put(key, list);
}
// 传进来的整个字符串数组遍历完了后,将 map 里边的所有值当做结果储存到一个 ArrayList<List<String>> 这个集合中
return new ArrayList<List<String>>(map.values());
}
}
题解分析
这道题要将字母异位词给组合在一起。首先要知道字母异位词是不同的词但所包含的字母类型和个数是一样的。因此,我们可以想到用 HashMap 来防止重复,看题目要求,结果要的是一个储存集合的数组集合中,所以可以用 ArrayList<List<String>>
来存储最终结果。
既然要使用 map 来储存结果,那么用什么来作为唯一的 key 呢?我们可以发现字母异位词不就是相同个数的相同字母不同顺序组合起来的单词,因此我们可以将单个字符串转成字符数组并排序,举个例子,假设传进来的字符串数组中有 eat 和 tea,按要求这两个要排序在一起的,怎么样才能让他们有相同的 key 呢?我们可以将其的 key 统一设置为按字母顺序的 aet,因此用到了 Arrays.sort
方法可以做到。不同的单词只要是字母异位词都会加到相同的键值对中,即在相同 key 的 map 中。
以此类推,将所有的字符串遍历完返回也就完成了字母异位词的组合。
leetcode原题:49. 字母异位词分组
评论区