6. Group Anagrams

MediumArray Hash Table String Sorting

Given an array of strings strs, group the words that are anagrams of each other (same letters, any order). Return the groups in any order; the words inside a group can also be in any order.

Example 1

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2

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

Example 3

Input: strs = ["a"]
Output: [["a"]]

Constraints

1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i] consists of 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