49. 字母异位词分组

解题思路

• 解法1
  1.首先是否为异位词，是字符串排序之后，是否相等即可判断
  2.用list存储排序之后的异位词，如果下次遍历到其他字符串，只需判断排序之后的字符串，list中是否包含此字符串即可
  3.用两个list来保存数据，一个用于存储排序之后的异位词数据，一个用于存储正常数据

*解法2
1.解法1中用了两个list来保存数据，每次用list的contains方法来判断
2.更加高校的解法为，用哈希表来存储关键数据，map的key为排序后的字符串，value为第几组数据

哈希解法.png

两种解法对比

用时和内存对比.png

解题遇到的问题

无

后续需要总结学习的知识点

无

##解法1
class Solution {
    public static List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> result = new ArrayList<List<String>>();
        List<List<String>> real = new ArrayList<List<String>>();

        if (strs.length == 0) {
            return result;
        }

        for (int i = 0; i < strs.length; i++) {
            boolean isContain = false;
            char[] cs = strs[i].toCharArray();
            Arrays.sort(cs);
            String str = String.valueOf(cs);
            for (int j = 0; j < result.size(); j++) {
                if (result.get(j).contains(str)) {
                    result.get(j).add(str);
                    real.get(j).add(strs[i]);
                    isContain = true;
                    break;
                }
            }
            if (!isContain) {
                List<String> temp = new ArrayList<String>();
                temp.add(str);
                result.add(temp);

                List<String> temp1 = new ArrayList<String>();
                temp1.add(strs[i]);
                real.add(temp1);
            }
        }
        return real;
    }
}

##解法2
public class Solution {
    /**
     * 字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母都恰好只用一次
     */
    public static List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> result = new ArrayList<>();
        if (strs.length == 0) {
            return result;
        }
        //将strs中的字符排序，如果字符串相等，则两个字符串为异位词
        //如何存储每个词的原始数据，以便于后面直接取到--首先想到用hashmap去存储，map的key为排序后的字符串，value为第几组数据
        Map<String, Integer> map = new HashMap<>();
        for (String str : strs) {
            //字符串排序
            char[] temp = str.toCharArray();
            Arrays.sort(temp);
            //此时的key为排序之后的字符串
            String key =String.valueOf(temp);
            //判断map中是否包含此可以
            if (map.containsKey(key)) {
                //如果包含，说明result中已经有此异位词相关的list列表，直接加入相应的列表即可
                result.get(map.get(key)).add(str);
            } else {
                //如何不包含，则将key加入map中
                map.put(key, result.size());
                //并且在result中新增list，用于保存当前新异位词的数组
                List<String> list = new ArrayList<>();
                list.add(str);
                result.add(list);
            }
        }
        return result;
    }

}