49 Group Anagrams

49. Group Anagrams

1. Question

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

2. Implementation

(1) HashMap + Sort

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<>();

        if (strs == null || strs.length == 0) {
            return res;
        }

        Map<String, List<String>> map = new HashMap<>();

        for (String str : strs) {
            char[] letters = str.toCharArray();
            Arrays.sort(letters);
            String key = new String(letters);

            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }

            map.get(key).add(str);
        }

        for (String key : map.keySet()) {
            res.add(map.get(key));
        }
        return res;
    }
}

(2) HashMap + Count Sort

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<>();

        if (strs == null || strs.length == 0) {
            return res;
        }

        Map<String, List<String>> map = new HashMap<>();

        for (String str : strs) { 
            int[] count = new int[256];
            for (char c : str.toCharArray()) {
                count[c]++;
            }

            StringBuilder key = new StringBuilder();
            for (char c = 0; c < 256; c++) {
                if (count[c] != 0) {
                    key.append(count[c]);
                    key.append(c);
                }
            }

            map.putIfAbsent(key.toString(), new ArrayList<>());
            map.get(key.toString()).add(str);
        }

        for (String key : map.keySet()) {
            res.add(map.get(key));
        }
        return res;
    }
}

3. Time & Space Complexity

HashMap + Sort: 时间复杂度O( m * nlogn), m是strs的长度, n是strs中最长string的长度，空间复杂度O(mn)

HashMap + Count Sort: 时间复杂度O(mn), 空间复杂度O(mn)