算法——LeetCode49. 字母异位词分组

tech2023-03-02  113

49. 字母异位词分组

原题链接

题目:

给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。

示例:

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

说明:

所有输入均为小写字母。不考虑答案输出的顺序。

题解1:排序数组分类

主要思想:

解题的核心是判断每个字符串是否为字母异位词方法是一个字符串当且仅当 其排序后的字符相同时 是一个字母异位词

代码:

这里注意一点 HashMap 使用的 key 字符串,必须不能使用toString() 方法创建的字符串,因为该方法每次创建的都是一个新对象,对于 map 中的 key 来说都是新的应该使用String.valueOf(chars)方法来创建,此时每次获取的对象都是字符串常量池中的对象,对 map 来说是一致的。 class Solution { public List<List<String>> groupAnagrams(String[] strs) { Map<String, List> map = new HashMap<>(); //遍历所有字符串 for (String s : strs) { //将String转为字符数组 char[] chars = s.toCharArray(); Arrays.sort(chars);//排序字符数组 //注意这里不能使用 toString() 方法,因为该方法每次都会创建一个新的String对象, //这会使 每次的 key 都不同,哪怕实际字符串内容是相同的 // String key=chars.toString(); String key = String.valueOf(chars); if (!map.containsKey(key)) {//若map中无该字符串,创建添加 List<String> list = new ArrayList<>(); list.add(s); map.put(key, list); } else {//之前已经有相应字符串,取出该list再添加该字符串即可 map.get(key).add(s); } } return new ArrayList(map.values()); } } 参考题解: https://leetcode-cn.com/problems/group-anagrams/solution/zi-mu-yi-wei-ci-fen-zu-by-leetcode/
最新回复(0)