GIVEN A LIST OF WORDS, GATHER THE ANAGRAMS INTO GROUPS. THE TRICK: COUNT THE LETTERS OF EACH WORD INTO A KEY. ANAGRAMS MAKE THE SAME KEY, SO THEY LAND ON THE SAME SHELF.
COUNT THE LETTERS OF EACH WORD INTO A KEY. WORDS WITH THE SAME KEY ARE ANAGRAMS, SO THEY GO ON THE SAME SHELF. RETURN THE SHELVES.
ONE PASS. BLUE IS THE WORD WE ARE ON. EACH SHELF IS ONE KEY. A NEW KEY OPENS A SHELF. GREEN MEANS THE WORD JOINS ONE.
1def group_anagrams(strs):2 groups = defaultdict(list) # from collections3 for s in strs:4 count = [0] * 265 for c in s:6 count[ord(c) - ord('a')] += 17 key = tuple(count)8 groups[key].append(s)9 return list(groups.values())
ONE PASS OVER N WORDS. EACH WORD OF LENGTH K DOES ONE LETTER COUNT. NO SORTING NEEDED.
EVERY WORD LANDS IN EXACTLY ONE GROUP, PLUS ONE 26-SLOT KEY PER GROUP.