剑指offer33：变位词组

题目：
给定一组单词，请将它们按照变位词分组。例如：输入一组单词[“eat”,“tea”,“tan”,“nat”,“bat”,“ate”],这组单词分为3组，分别是[“tea”,“ate”,“eat”],[“tan”,“nat”]和[“bat”]。
分析：
第一种思路是把每个英文小写字母映射到一个质数，例如a映射数字2，b映射数字3等等一直到z映射101（第26个质数）。单词“eat”可以映射到数字1562（11x2x71），如果同为变位词那么它们都会映射到相同数字，因此可以定义一个哈希表，哈希表的键是单词中字母映射的数字的乘积，而值为一组变位词。但是会出现一个潜在问题，由于把单词映射到数字用到了乘法，因此当单词非常长时可能会溢出。
第二种思路就是一组变位词映射到同一个单词，互为变位词的单词的字母出现的次数相同，把单词中的字母按字母表的顺序排序就会得到同一个字符串，因此可以定义一个哈希表，哈希表的键是按照字母顺序排列的字符串，值是一组变位词。
代码：

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.HashMap;
import java.util.linkedList;
import java.util.List;

public class GroupAnagrams {
//如果输入n个单词，平均每个单词由m个字母，那么第一种思路的时间复杂度是O（mn）
    public static List> groupAnagrams1(String[] strs) {
        int[] hash = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
        HashMap> groups = new HashMap<>();
        for (String str : strs) {
            long wordHash = 1;
            for (int i = 0; i < str.length(); i++) {
                wordHash *= hash[str.charAt(i) - 'a'];
            }
            //put与putIfAbsent区别:
//put在放入数据时，如果放入数据的key已经存在与Map中，最后放入的数据会覆盖之前存在的数据，
//而putIfAbsent在放入数据时，如果存在重复的key，那么putIfAbsent不会放入值。
            groups.putIfAbsent(wordHash, new linkedList());
            groups.get(wordHash).add(str);
        }
        return new linkedList<>(groups.values());
    }
    public static List> groupAnagrams2(String[] strs){
    //每个单词平均由m个单词，排序一个单词需要O（mlogm），如果每个单词由n个，该算法时间复杂度是O（nmlogn）
        HashMap> groups = new HashMap<>();
        for (String str : strs) {
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);
            String s = new String(charArray);
            groups.putIfAbsent(s,new linkedList());
            groups.get(s).add(str);
        }
        return new linkedList<>(groups.values());
    }

}