Topic · Hash MapMedium
Group Anagrams
Understand the problem
You're given an array of strings strs. Group together the strings that are anagrams of each other. Return the list of groups (the order within each group and the order between groups doesn't matter).
Example:
ts
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
output = [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]
// "eat", "tea", "ate" are in the same group because they're all anagrams of "aet"
// "tan", "nat" are in the same group because they're all anagrams of "ant"
// "bat" stands aloneThe task is to find a shared "signature" (key) for anagrams.
There are 2 ways to build the key: sort the word or count character frequencies.
Basic approach
O(n² · k log k) time, O(n) spacets
function groupAnagrams(strs: string[]): string[][] {
const groups: string[][] = []
const visited = new Set<number>()
for (let i = 0; i < strs.length; i++) {
if (visited.has(i)) continue
const group = [strs[i]]
const sorted = strs[i].split('').sort().join('')
for (let j = i + 1; j < strs.length; j++) {
if (visited.has(j)) continue
if (strs[j].split('').sort().join('') === sorted) {
group.push(strs[j])
visited.add(j)
}
}
groups.push(group)
}
return groups
}Why this approach is slow:
Two nested loops, and each comparison costs O(k log k) to sort a string of length k.
A Hash Map brings it down to a single O(n) loop.
Unlock the optimal solution, the step-by-step trace and related questions
See the full step-by-step trace, Big-O and edge cases.