// 整体思路：要归类到一起的字符串只是位置发生了变化，那排序一下不就一样了么；所以把每个字符串排序一下，然后把结果一样的放到一起就完事了（暴力

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 用来存储【排序后的字符列表】到【结果列表的index】的映射
        Map<List<Character>, Integer> map = new HashMap();
        // 结果列表，用来存储结果
        List<List<String>> res = new LinkedList();
        // 结果列表的index，从0开始
        int index = 0;

        // 对输入的字符串数组进行遍历
        for (int i = 0; i < strs.length; i++) {
            // 得到每一个字符串
            String str = strs[i];
            // 创建一个列表，用来将字符串拆解成字符，然后按照原来的顺序放到这个列表中
            List<Character> clist = new LinkedList();
            for (int j = 0; j < str.length(); j++) {
                char c = str.charAt(j);
                clist.add(c);
            }
            // 对这个字符串列表进行排序
            Collections.sort(clist);
            // 查找map中是否存在排序后的列表的Key，如果有，将正在处理的字符串插入到结果列表中映射对应的index中；如果没有，那么在结果列表中插入一个新的列表，并且在map中创建排序列表的key和它对应的在结果列表中的位置的value
            if (map.containsKey(clist)) {
                res.get(map.get(clist)).add(str);
            } else {
                map.put(clist, index);
                List<String> newList = new LinkedList();
                newList.add(str);
                res.add(newList);
                index++;
            }
        }
        return res;
    }
}