LeetCode-49. 字母异位词分组-Java实现

题目链接

题目

结果

1. 暴力思路

代码：

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> outterList = new ArrayList<>();
        if(strs==null||strs.length<=0){
            return outterList;
        }
        
        
        final String NULL = null;
        for(int i = 0;i < strs.length;i++){
            String target = strs[i];
            if(target==NULL){
                continue;
            }
            
            char[] targets = target.toCharArray();
            Arrays.sort(targets);
            
            List<String> innerList = new ArrayList<>();
            innerList.add(target);
            for(int j = i+1;j < strs.length;j++){
                String now = strs[j];
                if(now==null||now.length()!=target.length()){
                    continue;
                }
                char[] nows = now.toCharArray();
                Arrays.sort(nows);
                boolean judge = false;
                for(int k = 0;k < targets.length;k++){
                    if(targets[k]!=nows[k]){
                        judge = true;
                        break;
                    }
                }
                if(judge){
                    continue;
                }
                
                innerList.add(now);
                strs[j]=NULL;
            }
            outterList.add(innerList);
        }
        return outterList;
    }
}

官方题解

代码如下：

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> outerList = new ArrayList<>();
        Map<String,List<String>> map = new HashMap<>();

        for(int i =0;i < strs.length;i++){
            String target = strs[i];
            char[] chars = target.toCharArray();
            Arrays.sort(chars);
            String sortStr = String.valueOf(chars);
            List<String> innerList = null;
            if(!map.containsKey(sortStr)){
                innerList = new ArrayList<>();
                innerList.add(target);
                outerList.add(innerList);
                map.put(sortStr, innerList);
            }else{
                innerList = map.get(sortStr);
                innerList.add(target);
            }
        }
        return outerList;
    }
}

思路

脑子瓦特了，没有想到用map来去做，一开始就暴力法，我的暴力法是拿到一个，然后向后逐个比较，比较的时候要将两个字符串排序，排序后逐个位比较，如果一样放入list，并把后者在strs中置为null。
官方题解思路是：用一个map存储，map的键是字符串中每一位按字母表顺序排序后的结果，值为List，这个list用来装排序后为键值的原字符串，遍历字符串，每一个字符串排序，在map中查看是否有键为排序好的字符串，如果有则放入对应的list中，如果没有创建list，并放入。
两种思路比较后，暴力法每一个都要跟后面比，就这样时间复杂度就已经为O(NlogN)了，字符串的排序在每次比较中都要进行，这也是一个极大的性能损耗点，之后还要逐位比较（官方思路中是通过map存储，使用哈希算法，速度快），所以在时间上就差了几十倍。