-
Notifications
You must be signed in to change notification settings - Fork 0
034 — Group Anagrams
LeetCode 49 · Medium. Given an array of strings strs, group the anagrams together. You can return the answer in any order.
Imagine sorting a huge pile of mismatched socks into matching pairs, except instead of matching by color you have to match by "made of the exact same threads, just possibly woven in a different pattern." The naive move: hold up each sock next to every other sock and check thread-by-thread. The smart move: give every sock a label that's the same no matter how it was woven — say, "sort all its threads alphabetically" — and then just toss socks with matching labels into the same bin. Now grouping is just "look up the bin for this label," not "compare against every other sock."
"Group [things] together" where the grouping key isn't given directly but has to be derived from each item — here, "these strings are anagrams of each other" — is a signal to build a canonical key for each item and bucket items by that key in a hash map. Whenever you see "group by some property that requires normalizing the item first" (anagrams, same digits, same shape), the pattern is: compute a canonical form → Dictionary(key: canonical form, value: [original items]) → one pass, one bucket per unique canonical form.
For each string, scan through the groups formed so far and check if it's an anagram of the first string in any existing group (using the sorted-characters comparison from Valid Anagram). If a match is found, add it to that group; otherwise, start a new group.
func groupAnagramsBruteForce(_ strs: [String]) -> [[String]] {
var groups: [[String]] = []
for str in strs {
let sortedStr = str.sorted()
var placed = false
for i in 0..<groups.count {
if let first = groups[i].first, first.sorted() == sortedStr {
groups[i].append(str)
placed = true
break
}
}
if !placed {
groups.append([str])
}
}
return groups
}Big-O: O(n² · k log k) time, where n is the number of strings and k is the max string length — for each of the n strings, we may scan up to n existing groups, and each comparison re-sorts a string (O(k log k)). O(n · k) space for the groups.
Compute a canonical key for each string (its sorted characters) and use that key to bucket strings directly in a hash map — no scanning of existing groups required.
func groupAnagrams(_ strs: [String]) -> [[String]] {
var groups = [String: [String]]()
for str in strs {
let key = String(str.sorted()) // canonical form: same for every anagram
groups[key, default: []].append(str)
}
return Array(groups.values)
}Big-O: O(n · k log k) time — for each of the n strings, sorting its k characters to build the key. O(n · k) space for the map (keys plus stored strings).
The brute force re-derives "which group does this belong to?" by re-comparing against every group already formed — that linear scan over groups is the wasted work. Once you notice that anagrams all collapse to the same sorted string, that sorted string becomes a perfect hash-map key: instead of asking "is this an anagram of any existing group's representative?" (an O(n) scan), you ask "what bucket does this canonical key map to?" (an O(1) average lookup). Dropping the group-scanning n factor is exactly what takes O(n²·k log k) down to O(n·k log k).
- Hash Maps & Hash Sets — the canonical-key bucketing this solution is built on.
- Valid Anagram — the anagram-equivalence check this problem generalizes from "are these two an anagram pair?" to "group all pairs."
- Arrays & Strings — string traversal and sorting fundamentals.
-
Two Pointers — disclosed as a loose fit, not a natural one: this chapter's canonical-key step,
String(str.sorted())ingroupAnagrams, reuses the exact same sort-to-normalize idea as Valid Anagram — already linked above — and so inherits that chapter's same loose Two-Pointers echo one level removed: sorting to compare, rather than an explicit two-pointer comparison.
Group Anagrams is sorting socks by a thread-order label — give every item a canonical key, then just toss it in the matching bin.
The optimal solution's key is String(str.sorted()), costing O(k log k) per string. Suppose every string in strs is guaranteed to contain only lowercase English letters. Describe a canonical key you could compute in O(k) instead of O(k log k), and explain what it would look like for the string "aab".