Group a list of strings into anagram buckets
Given a list of strings, group the ones that are anagrams of each other (same letters, any order) into sublists. Return a list of those groups; group order does not matter.
Examples: ["eat","tea","tan","ate","nat","bat"] → [["bat"],["nat","tan"],["ate","eat","tea"]]; [""] → [[""]]; ["a"] → [["a"]].
def group_anagrams(strs: list[str]) -> list[list[str]]:
# your code hereWrite the implementation.
Bucket strings in a dict keyed by a canonical signature shared by all anagrams. The sorted-character tuple tuple(sorted(s)) works (or a 26-length letter-count tuple, which is O(n) per string instead of O(n log n)). Append each string to its key's list, then return list(d.values()).
- ✗Grouping by length, which merges non-anagrams
- ✗Keying by first letter or ASCII sum, which collides
- ✗Using an O(n^2) pairwise comparison instead of a key
- →Why is a letter-count key faster than sorting per string?
- →How does the empty-string case behave with your key?
All anagrams of a word share a canonical signature. Use it as a dict key and append each string to the matching bucket.
from collections import defaultdict
def group_anagrams(strs: list[str]) -> list[list[str]]:
buckets = defaultdict(list)
for s in strs:
key = tuple(sorted(s)) # or a 26-length letter-count tuple
buckets[key].append(s)
return list(buckets.values())"eat", "tea", "ate" all sort to ('a','e','t'), so they land in one bucket; "tan" and "nat" share ('a','n','t'); "bat" is alone. The empty string keys to () and forms its own group. Sorting is O(k log k) per string of length k; a letter-count tuple makes it O(k).
