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

2023-12-20 07:03:39

题目

一个字符串数组,请你将字母异位词组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

解法1:

思路:
遍历所有字符串,每个字符串进行排序然后作为key放在map中,这样排序后一样的字符串都会落下一个集合中。
public List<List> groupAnagrams(String[] strs) {

    if(strs==null||strs.length==0){
        return null;
    }
    List<List<String>> result = new ArrayList<>();
    HashMap<String,List<String>> map = new HashMap<>();


    for(String str : strs){
        //获取字符序列
        char[] chars = str.toCharArray();
        //排序
        Arrays.sort(chars);
        //排序后的字符串
        String sortStr = new String(chars);
        //以排序后的字符串为key,获取可以排序后获得当前字符串的集合
        List<String> existsList = map.getOrDefault(sortStr, new ArrayList<>());
        existsList.add(str);
        map.put(sortStr,existsList);
    }
    result.addAll(map.values());
    return result;
}

解法2:

思路:
计数法:每个字母出现的次数计数,然后作为key放在map中,得到一样key的字符串落下一个集合中
public List<List> groupAnagrams1(String[] strs) {

    if(strs==null||strs.length==0){
        return null;
    }
    List<List<String>> result = new ArrayList<>();
    HashMap<String,List<String>> map = new HashMap<>();
    for(String str : strs){
        int[] ctl = new int[26];
        char[] chars = str.toCharArray();
        //统计字符串字母出现的次数
        for(int i=0;i<chars.length;i++){
            ctl[chars[i]-'a']++;
        }

        StringBuffer stringBuffer = new StringBuffer();
        for(int i=0;i<26;i++){
            if(ctl[i]!=0){
                stringBuffer.append((char)'a'+i)
                        .append(ctl[i]);
            }
        }
        List<String> existsList = map.getOrDefault(stringBuffer.toString(), new ArrayList<>());
        existsList.add(str);
        map.put(stringBuffer.toString(),existsList);

    }
    result.addAll(map.values());
    return result;
}

文章来源:https://blog.csdn.net/qq_43599766/article/details/135095748
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。