Group Anagrams

The Idea

Two words are anagrams when their letters match and only the order differs. So give each word a canonical signature — its letters sorted — and use that signature as a dictionary key. Words sharing a signature drop into the same bucket, and no two words are ever compared directly.

Real-World Example

A locksmith sorts a drawer of cut keys by reading each blade's tooth depths and writing them down in a fixed order. Two keys stamped with rival brand names but the same depth code fall into one envelope. The code does the matching, not the eye.

The Code

def group_anagrams(words):
    groups = {}
    for w in words:
        key = "".join(sorted(w))              # canonical signature
        groups.setdefault(key, []).append(w)  # bucket by signature
    return list(groups.values())

print(group_anagrams(["listen", "silent", "enlist", "google"]))
# [['listen', 'silent', 'enlist'], ['google']]

groups = {}
for w in ["bat", "tab", "cat"]:
  k = "".join(sorted(w))
  groups.setdefault(k, []).append(w)
print(len(groups), len(groups["abt"]))