算法之异位词字符处理

关注

发布于: 2021 年 06 月 14 日

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

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

复制代码

解法一：将 String 按照字符 ascii 顺序映射成统一序的 String，作为 Map 的 key 键，以此归类进行分组时间复杂度:O(N*K)K 为内部每个单独 String 循环的时间复杂度

空间复杂度:为 O(1)

class Solution {    public List<List<String>> groupAnagrams(String[] strs) {        Map<String,List<String>> map = new HashMap<>();        for(String s : strs) {            int[] array = new int[26];            for(int i =0;i < s.length();i++) {                array[s.charAt(i) -'a']++;            }            String sHash = Arrays.toString(array);            if(!map.containsKey(sHash)) {                map.put(sHash, new ArrayList<String>());            }            map.get(sHash).add(s);        }        return new ArrayList<>(map.values());    }}

复制代码

解法二：对 String 的字符数组进行排序，或者统一序的 String 作为 Map 的 key 键，以此归类进行分组时间复杂度:O(N*KlogK)空间复杂度为 O(K)

public List<List<String>> groupAnagrams(String[] strs) {    if (strs == null || strs.length == 0) return new ArrayList<>();    Map<String, List<String>> map = new HashMap<>();    for (String s : strs) {        char[] ca = s.toCharArray();        Arrays.sort(ca);        String keyStr = String.valueOf(ca);        if (!map.containsKey(keyStr)) map.put(keyStr, new ArrayList<>());        map.get(keyStr).add(s);    }    return new ArrayList<>(map.values());}

复制代码

两种解法思路基本一致，不过在于对原始字符的识别处理上不一样。第一种对于任意长度的数据，只需要一次遍历 O(n)即可实现，其优点在于对于长字符支持较好。

发布于: 2021 年 06 月 14 日阅读数: 13

原文链接:【http://xie.infoq.cn/article/40637906011dfc6f3dac7f81b】。文章转载请联系作者。

Skysper

关注

人生不在于谁更优秀，而在于谁更坚持 2016.03.29 加入

还未添加个人简介

发布

暂无评论

创作场景

算法之异位词字符处理

Skysper

评论