49. Group Anagrams

题目分析

Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note: All inputs will be in lower-case.

代码一

时间复杂度为 O(m * n * log(n))，空间复杂度为 O(n)

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<>();
        if(strs == null || strs.length == 0) return res;
        HashMap<String, Integer> map = new HashMap<>();
        for(String str : strs) {
            // 将每个字符串转成字符数组，然后排序，再转成字符串
            char[] temp = str.toCharArray();
            Arrays.sort(temp);
            String s = new String(temp);
            // 判断这个字符串是不是已经出现过了
            if(map.containsKey(s)) {
                res.get(map.get(s)).add(str);
            } else {
                // 新建一个list，添加该字符串
                ArrayList<String> list = new ArrayList<>();
                list.add(str);
                // 将字符串放到 map 中，位置填当前 res 的长度
                map.put(s, res.size());
                // res 添加 list
                res.add(list);
            }
        }
        return res;
    }
}

代码二

时间复杂度O(mn)

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<>();
        if(strs == null || strs.length == 0) return res;
        HashMap<String, List<String>> map = new HashMap<>();
        for(String str : strs) {
            int[] count = new int[26];
            for(char c : str.toCharArray()) {
                count[c - 'a'] ++;
            }
            String s = "";
            for(int i = 0; i < count.length; i++) {
                s += String.valueOf(count[i]) + String.valueOf(i + 'a');
            }
            if(map.containsKey(s)) {
                map.get(s).add(str);
            } else {
                List<String> list = new ArrayList<>();
                list.add(str);
                map.put(s, list);
            }
        }
        return new ArrayList<List<String>>(map.values());
    }
}