49. 字母异位词分组 (opens new window)

1.哈希+字符串排序

分析：关键在于如何设计每个字母异位词的哈希key。

互为字母异位词的每个单词中，每个字符出现的次数都是相同的，仅仅只是排序的方式不同。此处使用哈希来对每个字母异位词进行聚类，对于每一个字母异位词而言，将它们按照每个字符的字典序的方式进行排序后，得到的字符串一定都是相同的。其中key为按照字典序排序后的字符串，value为字母异位词集合。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res=new ArrayList<>();
        Map<String,List<String>> map=new HashMap<>();
        for(int i=0;i<strs.length;i++){
            char[] chars=strs[i].toCharArray();
            Arrays.sort(chars);
            String temp=new String(chars);
            if(map.containsKey(temp)){
                map.get(temp).add(strs[i]);
            }
            else{
                map.put(temp,new ArrayList<String>(Arrays.asList(strs[i])));
            }
        }

        for(List<String> list:map.values()){
            res.add(list);
        }
        return res;
    }
}