Group Anagrams
Given a list of strings, group the anagrams together and return a list of these groups in any order.
Two strings are anagrams if you can rearrange the letters of one to form the other, without adding or losing any letters.
Examples
s: ["eat", "tea", "tan", "ate", "nat", "bat"] output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]] s: ["listen", "silent", "enlist", "google", "gooegl"] output: [["listen", "silent", "enlist"], ["google", "gooegl"]] s:[""] output: [""] s: ["p"] output: ["p"]
Algorithm
Character Frequency Signature: For each word, create a 26-length list (for each lowercase English letter) that counts how many times each character appears.
Use as a Hash Key: Convert this frequency list into a tuple so it can be used as a dictionary key. This tuple uniquely identifies the anagram group the word belongs to.
Group in Dictionary: Use a dictionary to collect all words that share the same character frequency signature.
Return Result: Return the values of the dictionary, where each value is a list of strings that are anagrams of one another. These grouped lists represent the final output.
from typing import List
import collections
def group_anagrams(strs: List[str]) -> List[List[str]]:
res = collections.defaultdict(list)
for string in strs:
count = [0] * 26
for c in string:
count[ord(c) - ord("a")] += 1
res[tuple(count)].append(string)
return list(res.values())Time Complexity: O(N⋅K), where N is the number of strings and K is the maximum length of a string.
Space Complexity: O(N⋅K), to store the grouped anagrams and their frequency signatures.