Group Anagrams

MediumArray Hash Table String Sorting

A word-puzzle app wants to show players which words can be spelled from the same set of letter tiles. Two words share a set of tiles when they are anagrams: the same letters, each used the same number of times, possibly in a different order.

Given an array of lowercase words strs, sort the words into such groups and return the list of groups. Every word belongs to exactly one group, so all copies of a repeated word end up together. Words may be empty, and all empty words share one group. The groups can be returned in any order, and so can the words inside each group.

Example 1

Input: strs = ["race","care","acre","bat","tab","sun"]
Output: [["race","care","acre"],["bat","tab"],["sun"]]

Explanation: race, care and acre each use one a, c, e and r. sun has no partner, so it forms a group of one.

Example 2

Input: strs = ["loop","pool","polo","lop"]
Output: [["loop","pool","polo"],["lop"]]

Explanation: lop has only one o, so it is not an anagram of the other three.

Example 3

Input: strs = ["x","","x"]
Output: [["x","x"],[""]]

Explanation: Both copies of x land in the same group, and the empty word gets a group of its own.

Constraints

strs contains between 1 and 10^4 words.
Each word is 0 to 100 characters long and uses only lowercase English letters.

💡 Hint 1

Two words are anagrams exactly when their sorted letters are equal.

💡 Hint 2

Use that canonical form as a hash-map key. For O(k) keys, count the 26 letters instead of sorting.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Map each word to a canonical key, its letters sorted, and collect words with the same key in a hash map. Return the map's values. Sorting each word costs O(k log k); counting letters into a 26-length signature brings it to O(k).

Time O(n · k log k) for n words of length kSpace O(n · k)

function groupAnagrams(strs) {
  const groups = new Map();
  for (const s of strs) {
    const key = [...s].sort().join('');
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(s);
  }
  return [...groups.values()];
}

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String s : strs) {
            char[] c = s.toCharArray();
            Arrays.sort(c);
            groups.computeIfAbsent(new String(c), k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(groups.values());
    }
}

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
function groupAnagrams(strs) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit