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

LeetCode变位词组

news 来源：原创 2024/5/20 12:42:50

剑指 Offer II 033. 变位词组

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

注意：若两个字符串中每个字符出现的次数都相同，则称它们互为变位词。

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

来源：LeetCode

题目的关键点就在于统计每个字符出现的次数，可以将每个字符以及字符出现的次数作为map集合的key。
统计字母个数的时侯将元素中的每一个字母的个数记录在长度为26的int数组中,对于每个元素都要进行这个过程。

思路总结：
1.对于每一个strs中的字符串，在count数组中存储其每个字母的个数，故count数组应该大小为26.
2.将元素的每个字母以及其出现的次数进行拼接作为map集合的key，方便后续判断是不是变位词。
3.将具有相同key值的元素加入到list集合里面，此时要注意，如果是还没有对应的key值，那应该新建一个List；如果有相应的key值，就将当前字符串加入到list集合里面。
4.map集合的key就是上面的key，value就是对应的list集合的值，每次遍历一个strs中的元素都要更新一次。
5.最后返回map集合中的value即可。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map = new HashMap<String,List<String>>();
        for(String str:strs){
            int[] count = new int[26];
            int length = str.length();

            for(int i=0;i<length;i++){
                count[str.charAt(i)-'a']++;
            }

            StringBuffer s = new StringBuffer();
            for(int i=0;i<26;i++){
                if(count[i]!=0){
                    s.append('a'+i);
                    s.append(count[i]);
                }    
            }
            String key = s.toString();
            List<String> list = map.getOrDefault(key,new ArrayList<String>());
            list.add(str);
            map.put(key,list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}