49. Group Anagrams

LeetCode

BruteForce

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> result = new ArrayList<>();
        int n = strs.length;
        boolean[] seen = new boolean[n];

        if (n == 0) return result;

        for (int i = 0; i < n; i++) {
            if (seen[i]) continue;

            List<String> group = new ArrayList<>();
            group.add(strs[i]);
            seen[i] = true;

            for (int j = i + 1; j < n; j++) {
                if (!seen[j] && isAnagram(strs[i], strs[j])) {
                    group.add(strs[j]);
                    seen[j] = true;
                }
            }

            result.add(group);
        }

        return result;
    }

    private boolean isAnagram(String a, String b) {
        if (a.length() != b.length()) return false;

        int[] count = new int[26];
        for (char c : a.toCharArray()) count[c - 'a']++;
        for (char c : b.toCharArray()) count[c - 'a']--;
        for (int x : count) {
            if (x != 0) return false;
        }
        return true;
    }
}

Remarks:

  1. TC: $O(n^2\times L)$, SC: $O(n\times L)$. $L$ is the average length of each strings. VERY SLOW!

HashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();

        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);  // sorted string as the key

            map.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
        }

        return new ArrayList<>(map.values());
    }
}

Remarks:

  1. Key point: we can arrange the strings. Anagrams will become same after sorted, can have same hash value.
  2. TC: $O(n\times L \log L)$, SC: $O(n\times L)$
  3. return new ArrayList<>(map.values()); has the type of List<List<String>>.
  4. map.computeIfAbsent(key, k -> new ArrayList<>()).add(str); is same as:
    1
    2
    3
    4
    if (!map.containsKey(key)) {
     map.put(key, new ArrayList<>());
    }
    map.get(key).add(str);