leetcode-group-anagrams

题目大意

　　https://leetcode.com/problems/anagrams/

　　给你字符串数组，我们规定字符顺序变换的字符串为一组，输出所有组。

题目分析

　　利用HashMap，key为字符串排序后的结果（这样才能字符顺序不同的字符串的key值相同），value就是字符串数组就行。因此计算key的开销就是len * log(len)，len为字符串的长度。看了disscuss区最优解法，由于字母只有26个，因此映射成26个素数，用素数的乘积做为key，也可以保证key的唯一合理性。下面贴出了我的原始的做法。

代码

public class Solution {
    
    private String strSort(String s) {
        char[] array = s.toCharArray();
        Arrays.sort(array);
        return new String(array);
    }
    
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> ans = new ArrayList<List<String>>();
        if (strs == null || strs.length == 0) {
            return ans;
        }
        int len = strs.length;
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (int i = 0; i < len; i++) {
            String s = strSort(strs[i]);
            if (map.containsKey(s)) {
                List<String> list = map.get(s);
                list.add(strs[i]);
            } else {
                List<String> list = new ArrayList<String>();
                list.add(strs[i]);
                map.put(s, list);
            }
        }
        for (String key : map.keySet()) {
            ans.add(map.get(key));
        }
        return ans;
    }
}

　　时间复杂度：O(n len log(len))，n为数组长度，len为数组中字符串“平均”长度