博客

题目：

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

示例:

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

说明：

• 所有输入均为小写字母。
• 不考虑答案输出的顺序。

思路：（以下有三种方法，第一、二中方法都超时！！，第一种是自己的思路，两外两种是其他人的思想+自己理解）

方法一：遍历strs[i]，用j遍历reslut的大小， 判断当前字符串是否是result.get(j)的字母异位词，是的话，加到result.get(j)后面，不是的话，新增一个sub，加到result后面。（这种笨方法超时，最后一个测试用例不能通过）

代码：

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> result = new ArrayList<List<String>>();
        if (strs.length == 0){
            return result;
        }else{
            List<String> sub = new ArrayList<String>();
            sub.add(strs[0]);
            result.add(sub);
        }
        for (int i = 1; i < strs.length; i++){//遍历字符串数组strs的大小
            int flag = 0;
            for(int j = 0; j < result.size(); j++){//遍历result的大小
                if (check(strs[i], result.get(j).get(0))){//判断当前字符串是否是result.get(j)的字母异位词
                    result.get(j).add(strs[i]);//是的话，加到result.get(j)后面
                    flag = 1;
                }
            }
            if (flag == 0){//不是的话，新增一个sub，加到result后面
                List<String> sub = new ArrayList<String>();
                sub.add(strs[i]);
                result.add(sub);

            }
        }
        return result;
    }

方法二： 在strs里拿出来一个strs[i]，转成字符数组ch，对它进行排序ch，排序后的序列ch，在result中找有没有相同的ch1，有的话把拿出来那个strs[i]放到排序后相同的那一列，没有的话另起一列放strs[i]（也超时，最后一个测试用例不能通过）

代码：

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        //在strs里拿出来一个，对它进行排序，排序后的序列，在result中找有没有相同的，
        //有的话把拿出来那个strs[i]放到排序后相同的那以列
        //没有的话另起一列
        List<List<String>> result = new ArrayList<List<String>>();
        if (strs.length == 0){
            return result;
        }
        for (int i = 0; i < strs.length; i++){
            String str = strs[i];//在strs中拿出一个strs[i]
            char[] ch = str.toCharArray();//字符串转字符数组
            Arrays.sort(ch);//对字符数组排序
            int flag = 0;
            for(int j = 0; j < result.size(); j++){
                String str1 = result.get(j).get(0);//把每一行的第一个字符串拿出来
                char[] ch1 = str1.toCharArray();//转成字符数组
                Arrays.sort(ch1);//排序
                if (Arrays.equals(ch, ch1)){//比较strs[i]和每一行的第一个字符串是否是字母异位词
                    result.get(j).add(result.get(j).size(), strs[i]);//是的话，把strs[i]放到这一行的后面
                    flag = 1;
                    break;
                }

            }
            if (flag == 0){//strs[i]和每一行的第一个字符串都不是字母异位词的话，另起一行，把strs[i]放在这一行
                List<String> sub = new ArrayList<String>();
                sub.add(strs[i]);
                result.add(sub);
            }
        }
        return result;
    }
}

方法三：在strs中拿出一个strs[i], 转成字符数组ch，排序ch，字符数组再转成字符串str_ch， 排序后的字符串str_ch视为key值，若key值匹配，则将strs[i]加到key对应的value后面，最后把map的value值放到result里。

代码：

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        //在strs中拿出一个strs[i],转成字符数组，排序，字符数组再转成字符串，
        //排序后的字符串视为key值，若key值匹配，则将strs[i]加到
        //key对应的value后面
        List<List<String>> result = new ArrayList<List<String>>();
        Map<String, List<String>> map = new HashMap<String, List<String>>();

        for(int i = 0; i < strs.length; i++){
            String str = strs[i];
            char[] ch = str.toCharArray();//字符串转字符数组
            Arrays.sort(ch);//排序
            String str_ch = String.valueOf(ch);//转成字符串
            if(map.containsKey(str_ch)){//有匹配的key值

                map.get(str_ch).add(strs[i]);

            }else{//没有匹配的key值
                List<String> temp =  new ArrayList<>();
                temp.add(strs[i]);
                map.put(str_ch, temp);
            }
        }
        for (List<String> sub : map.values()){
            result.add(sub);
        }
        return result;
    }
}