当前位置：首页 > article >正文

字母异位词分组力扣49

article 2025/3/11 2:32:05

一、题目

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

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

示例 1:

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

示例 2:

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

示例 3:

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

二、思路

由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。

例如" ate" "tea" "eat"排序后的结果都是" aet "。那么我们就可以把排序后的结果作为map的键，将这些排序后相等的字符串，用list存入，作为map的值，最后返回这些值即可。

三、代码

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
       
        //最关键的思路就是每一组字母异位词排序后的单词顺序是一样的，这才是最关键的
        //1.定义一个map集合存放以排序后的单词为key，以单词本身为value的字符串集合
        Map<String, List<String>> map = new HashMap<>();
        //2.遍历字符串数组
        for (String str : strs) {
            char[] chars = str.toCharArray();
            //3.将该单词按照字母顺序排序
            Arrays.sort(chars);
            //4.将排序后的单词作为key，以单词本身为value的字符串集合作为value，存入map集合中
            String key = new String(chars);
            //5.如果map集合中已经存在该key，则将value添加到该key对应的字符串集合中
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            //6.将value添加到该key对应的字符串集合中
            list.add(str);
            //7.将key和value存入map集合中
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values()); //将map集合中的value存入一个字符串集合中，并返回该集合
    }
}

详细分析：

初始化一个空的 HashMap map。
遍历字符串数组 strs。对第一个字符串 "eat"执行:
将 "eat" 转换为字符数组 ['e', 'a', 't']
对字符数组进行排序,得到 ['a', 'e', 't']
使用排序后的字符数组创建 key "aet"
从 map 中获取 key 为 "aet" 的值,由于不存在,因此创建一个新的空列表 list = []
将 "eat" 添加到 list 中,现在 list = ["eat"]
将 key 为 "aet",value 为 ["eat"] 的键值对存入 map
对第二个字符串 "tea" 执行类似操作:
字符数组为 ['t', 'e', 'a'],排序后为 ['a', 'e', 't'],key 为 "aet"
从 map 中获取 key 为 "aet" 的值,存在,为 ["eat"]
将 "tea" 添加到列表中,现在列表为 ["eat", "tea"]
将更新后的列表存入 map,key 为 "aet"
对其余字符串 "tan", "ate", "nat", "bat" 执行类似操作,最终 map 为:
key 为 "aet",value 为 ["eat", "tea", "ate"]
key 为 "ant",value 为 ["tan", "nat"]
key 为 "abt",value 为 ["bat"]
从 map 中获取所有 value,构造结果列表,即 [ ["eat", "tea", "ate"], ["tan", "nat"], ["bat"] ]
可以看到,通过将每个字符串排序作为 key,并存储字母异位词的字符串列表作为 value,算法成功将字母异位词分组了。这样的分组过程更加高效,避免了对每个字符串都进行两两比较的低效操作。