大家好！我是曾续缘💓

今天是《LeetCode 热题 100》系列

发车第 2 天

哈希第 2 题

❤️点赞 👍 收藏 ⭐再看，养成习惯

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

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

示例 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] 仅包含小写字母

难度：💖💖

思路

题目要求我们对多个字符串进行分组，字符串中字母的种类相同并且每个种类的数量相等的互为字母异位词，归为同一组。

如何判断两个字符串的字母种类相同并且每个种类的数量相等呢？

使用排序，排序后字母种类+数量按统一的顺序排列，如果种类相同并且数量相等，将得到相同的字母排列，根据这个特点可以进行分组。

解题方法

使用哈希表将字母异位词映射到同一个分组, 在不改变哈希表的映射函数的情况下, 我们让字母异位词获得同样的key, 将字母异位词排序后可以得到相同的字符串, 作为key后得到对应的分组, 然后添加即可.

Code

查看代码

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> mp = new HashMap<String, List<String>>();
        for(String str : strs){
            char[] a = str.toCharArray();
            Arrays.sort(a);
            String key = new String(a);
            List<String> list = mp.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            mp.put(key, list);
        }
        return new ArrayList<List<String>>(mp.values());
    }
}