Group Anagrams

NeetCode: Group Anagrams · LeetCode: 49. Group Anagrams · Difficulty: Medium

Given an array of lowercase strings, group the anagrams together. The groups and the strings inside each group can be returned in any order.

Example

Text

Input:  strs = ["act", "pots", "tops", "cat", "stop", "hat"]
Output: [["hat"], ["act", "cat"], ["stop", "pots", "tops"]]

Brute force: compare against every group

Keep a list of groups. For each string, scan the existing groups and compare it with the first member of each (using the sorting check from Valid Anagram). Join the first group that matches, or start a new one.

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    private boolean isAnagram(String a, String b) {
        char[] x = a.toCharArray();
        char[] y = b.toCharArray();
        Arrays.sort(x);
        Arrays.sort(y);
        return Arrays.equals(x, y);
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> groups = new ArrayList<>();
        for (String s : strs) {
            boolean placed = false;
            for (List<String> g : groups) {
                if (isAnagram(g.get(0), s)) {
                    g.add(s);
                    placed = true;
                    break;
                }
            }
            if (!placed) {
                List<String> g = new ArrayList<>();
                g.add(s);
                groups.add(g);
            }
        }
        return groups;
    }
}

public class Main {
    public static void main(String[] args) {
        String[] strs = {"act", "pots", "tops", "cat", "stop", "hat"};
        System.out.println(new Solution().groupAnagrams(strs));
    }
}

Output

[[act, cat], [pots, tops, stop], [hat]]

Time: O(n · g · k log k) where g is the number of groups and k the string length, which is O(n²) in the worst case. Space: O(n · k).

Optimal: group by a canonical key

All anagrams share the same letter counts, so the counts make a perfect dictionary key. Build an int[26] count array for each word and turn it into a String with Arrays.toString to use as the HashMap key. An int[] cannot be the key directly: arrays use identity for equals and hashCode, so two arrays with the same counts would count as different keys. Words with the same key text land in the same group. computeIfAbsent creates the group list the first time a key appears.

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String s : strs) {
            int[] count = new int[26];
            for (int i = 0; i < s.length(); i++) {
                count[s.charAt(i) - 'a']++;
            }
            String key = Arrays.toString(count); // an int[] has identity equality, so use its text as the key
            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(groups.values());
    }
}

public class Main {
    public static void main(String[] args) {
        String[] strs = {"act", "pots", "tops", "cat", "stop", "hat"};
        List<List<String>> result = new Solution().groupAnagrams(strs);
        // HashMap order is unspecified, so sort the groups by their first word for a stable printout.
        result.sort(Comparator.comparing(g -> g.get(0)));
        System.out.println(result);
    }
}

Output

[[act, cat], [hat], [pots, tops, stop]]

Time: O(n · k) for n strings of length up to k. Space: O(n · k).

Using the sorted letters of each word as the key also works, at O(n · k log k); the count array avoids the sort. The count key text has a fixed length of 26 numbers, so building and hashing it is O(k + 26) per word.