49.md

#49. Group Anagrams 题目链接 ##解法一 用java8的新特性，lambda表达式和stream来解决问题，这样用一行代码就可以了，但是缺点是运行速度特别慢，是因为stream的性能不好吗？

java stream 性能探索

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        return Arrays.stream(strs)
                .collect(Collectors.groupingBy(n -> n.chars().sorted().reduce((sum,num) -> 100 * sum + (num-'a'+1))))
                .values().stream().collect(Collectors.toList());
    }
}

经过调查之后，stream的性能在某些情况下会不好，所以将stream展开，得到如下代码

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> result= new ArrayList<>();
        Map<String, ArrayList<String>> line = new HashMap<>();
        for(int i = 0; i < strs.length; i++) {
            char c[] = strs[i].toCharArray();
            Arrays.sort(c);
            String key = String.valueOf(c);
            if (line.containsKey(key)) {
                ArrayList<String> temp = line.get(key);
                temp.add(strs[i]);
            }
            else {
                ArrayList<String> temp = new ArrayList<>();
                temp.add(strs[i]);
                line.put(key, temp);
            }
        }
        result.addAll(line.values());
        return result;
    }
}

上面代码跑测试用例只用了20s，比stream提升了6倍之多

还有一种质数的方法，把代码拷贝过来，留作备用

public static List<List<String>> groupAnagrams(String[] strs) { 
   int[] prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103};//最多10609个z
    
            List<List<String>> res = new ArrayList<>();
            HashMap<Integer, Integer> map = new HashMap<>();
            for (String s : strs) {
                int key = 1;
                for (char c : s.toCharArray()) {
                    key *= prime[c - 'a'];
                }
                List<String> t;
                if (map.containsKey(key)) {
                    t = res.get(map.get(key));
                } else {
                    t = new ArrayList<>();
                    res.add(t);
                    map.put(key, res.size() - 1);
                }
                t.add(s);
            }
            return res;
    }