[数据结构与算法]LeetCode第49题 字母异位词分组

第一反应

先写一个函数，用于对比两个词是否为异位词
然后每拿到一个新的词，就依次和前面保存的答案数组中的每一个词对比，如果有相同的就放进去，如果没有就单独成组放进去。
效率不高，要执行n^2次那个对比词的函数

看看题解

题解给了一个不错的方案。只要计数每个字母出现的次数就行。如果两个词中字母出现的次数一样，就存放在同一个列表里。

提交通过

试了一下用内部类作为结构体的写法，提交通过了，但是时间和内存消耗都太大了

class Solution {
    public class WordAndArr{
        public int[] chArr;
        public List<String> words;
        public WordAndArr(int[] inp){
            chArr = inp;
            words = new ArrayList<>();
        }
        public boolean checkEquals(int[] inp){
            for(int i = 0 ; i < 26 ; i ++){
                if(chArr[i] != inp[i]){
                    return false;
                }
            }
            return true;
        }
        public void print(){
            System.out.println("----------");
            for(int i = 0 ; i < 26 ; i ++){
                if(chArr[i] != 0){
                    System.out.println("chArr[" + i + "] = " + chArr[i]);
                }
            }
            for(String value:words){
                System.out.print(value + "  ");
            }
            System.out.println();
        }
    }
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> ans = new ArrayList<>();
        int ansIndex = 0;
        List<WordAndArr> save = new ArrayList<>();
        for(int i = 0 , len = strs.length; i < len ; i ++){
            int[] chArr = wordToArray(strs[i]);
            boolean isNew = true;
            for(WordAndArr struct:save){
                if(struct.checkEquals(chArr)){
                    struct.words.add(strs[i]);
                    struct.print();
                    isNew = false;
                    break;
                }
            }
            if(isNew){
                WordAndArr wordAndArr = new WordAndArr(chArr);
                wordAndArr.words.add(strs[i]);
                wordAndArr.print();
                save.add(wordAndArr);
                
            }
        }
        for(WordAndArr wordAndArr:save){
            ans.add(wordAndArr.words);
        }
        return ans;

        // return null;
    }
    public int[] wordToArray(String word){
        int[] chArr = new int[26];
        for(int i = 0,len = word.length() ; i < len ; i ++){
            chArr[word.charAt(i) - 'a'] ++;
        } 
        return chArr;
    }
}