"""
https://leetcode.com/problems/group-anagrams/description/
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
"""
from collections import defaultdict
from typing import List
def group_anagrams(arr: List[str]) -> List[List[int]]:
hashes = defaultdict(list)
for i, word in enumerate(arr):
key = [0] * 26
for c in word:
key[ord(c) - ord("a")] += 1
hashes[tuple(key)].append(word)
return list(hashes.values())
Tests
from publicmatt.leet.problems.group_anagrams import group_anagrams
def test_simple_grouping():
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
ans = [["bat"], ["tan", "nat"], ["eat", "tea", "ate"]]
for group in group_anagrams(strs):
assert group in ans
def test_empty():
strs = [""]
ans = [[""]]
assert group_anagrams(strs) == ans
def test_single_group():
strs = ["a"]
ans = [["a"]]
assert group_anagrams(strs) == ans