字母异位词分组

字母异位词分组

题目描述

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

• 字母异位词：是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例

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

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

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

解析

哈希表 + 排序：

• 创建哈希表，key 存储排序好的模版， value 存储实际的异位词
• 遍历字符串集合，将字符串元素转换为 char 数组通过 sort 函数排序，排序后通过 toString 函数转换成字符串
• 判断该字符串是否存在哈希表中，不存在则创建该元素哈希键，在将该元素存放在 value 中
• 遍历结束后，哈希表的 values 函数返回哈希表中所有的值

代码

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = Arrays.toString(chars);

            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(str);
        }
        return new ArrayList<>(map.values());
    }
}