java实现49. 字母异位词分组，一错再错，总结一下

438. 找到字符串中所有字母异位词
 第一次提交：“暴力求解？”

 后面看了题解之后：“哦，原来还可以这样”

 二刷看到这个题我一脸懵，“暴力求解？”于是乎：

 我先贴一个我超时的代码（两次超时代码一摸一样，醉了），总结一下我错哪。看题解的小伙伴可以直接跳过这段。
我的思路大概是这样的，两层for循环遍历求解，中间核心代码是用isSome(String s,String t)判断两个字符串是不是字母异位词，用了两种方法来尽量减少暴力求解的用时，第一个是再判断是不是字母异位词的时候用长度26的整形数组做哈希表。第二个是将已经分组的字符串置为null，下次直接跳过。后面看了超时的测试用例，果然是不让我钻空子。我自己也思考了，如果说这些单词里面压根没有字母异位词的话，我这种解法就是O(N平方)的。确实粗鲁了。在写不出的时候我也产生了两个疑问：第一个是判断两个字符串是不是字母异位词除了用数组做哈希表还有更简单的求法吗？，第二个是要将测试用例中的字符串两两对比，除了暴力对比之外还有更简单的方法吗？

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> result = new ArrayList<>();
        for(int i = 0 ; i< strs.length ;i++){
            if(strs[i] != null){//为空说明分好组了。跳过。
                List<String> temp = new ArrayList<>();
                temp.add(strs[i]);
                for(int j = i+1 ; j< strs.length ;j++){
                    if(strs[j] != null){//为空说明分好组了。跳过。
                        if(isSome(strs[i],strs[j])){//核心的判断代码
                            temp.add(strs[j]);
                            strs[j] = null;//分好组之后置为空
                        }
                    }
                }
                result.add(temp);
            }
        }
        return result;
    }
    public boolean isSome(String s,String t){
        int[] arr = new int[26];
        for(char data : s.toCharArray()){
            arr[data - 'a']++;
        }
        for(char data : t.toCharArray()){
            if(--arr[data - 'a'] < 0){
                return false;
            }
        }
        for(int data : arr){
            if(data > 0){
                return false;
            }
        }
        return true;
    }
}

题解1：

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();//哈希表，key为排序后的字符串，value为分组
        
        for(String data : strs){//一次遍历字符串数组
            char[] temp = data.toCharArray();//排序字符串
            Arrays.sort(temp);
            String temp1 = new String(temp);
            List<String> list = map.getOrDefault(temp1,new ArrayList<String>());//利用map做分组
            list.add(data);//这里装的是没有排序过的字符串。
            map.put(temp1, list);//如上述，key为排序后的字符串，value为分组
        }
        return new ArrayList<List<String>>(map.values());
    }
}

 看完这个题解之后，“漂亮”。解决我自己两个疑惑，第一，可以使用字符串排序的方法判断是不是字母异位词。利用map结构，以排序后的字符串为公共值（key），将相同的全部收进value。（判断两两（或两个以上）是否相等，可以利用map结构，将相同点作为key，用value来收录，只需一次遍历。）

题解2：
在上个题解的基础上，公共值（key）改成了每个字符串中：字符+字符出现次数。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();//哈希表，key为排序后的字符串，value为分组
        for(String data : strs){//一次遍历字符串数组
            int[] arr = new int[26];
           for(char temp : data.toCharArray()){
               arr[temp - 'a']++;
           }
           StringBuilder str = new StringBuilder();//拼凑出公共值（key）字符+字符出现次数的形式
           for(int i = 0; i < 26; ++i){
               if(arr[i] > 0){
                   str.append((char)(i + 'a'));
                   str.append(arr[i]);
               }
           }
           String temp = str.toString();
           List<String> list = map.getOrDefault(temp, new ArrayList<>());
           list.add(data);
           map.put(temp, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

 我自己有一个思考不知道对不对，关于题解1中字符串的排序，使用的是Arrarys.sort()方法，无论是小数量的插排还是大数量的快排，这些排序算法最优时间复杂度是O(N*logN)，但是如果使用下面这种方法，对字符串的排序其实可以达到O(N)；
 首先遍历一次字符串（用整形数组做哈希表），用时N。遍历数组按照大小取值，用时N+26。总的来不就是2N+26，O(N)的时间复杂度嘛。

int[] arr = new int[26];
for(char c : data.toCharArray()){
 	 arr[c - 'a']++;
}
StringBuilder str = new StringBuilder();
int i = 0;
while( i < 26){
	if(arr[i] > 0){
		str.append((char)(i + 'a'));
    	arr[i]--;
    	continue;
    }
    i++;
}
String temp1 = str.toString();