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.
# ========================================== # Complexity Analysis # ========================================== # Time Complexity: O(N * K) # - N is the number of strings, and K is the maximum length of a string. # - We iterate through every string, and for each string, we iterate through # its characters to build a frequency array. # # Space Complexity: O(N * K) # - We store N strings of max length K inside our hash map. # - In the worst case (no anagrams), we also store N distinct tuple keys. # Since each tuple is always size 26, the key storage is O(N * 26) -> O(N). # The total space is dominated by storing the actual strings: O(N * K). # ========================================== class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: # "I'll start by initializing a standard hash map. The key will be the # character frequency signature, and the value will be a list of the anagrams." hm = {} # "We'll process each string in our input array one by one." for s in strs: # "To achieve O(N*K) time, instead of sorting, I'll create a frequency # array of size 26 to count the occurrences of each lowercase letter." count = [0] * 26 # "I'll iterate through every character in the current string, mapping # its ASCII value to a 0-25 index using 'ord' to increment the count." for c in s: count[ord(c) - ord("a")] += 1 # "Since standard lists are mutable in Python, they cannot be hashed # as dictionary keys. I'll cast the frequency array to an immutable tuple." key = tuple(count) # "If we have seen this exact character frequency signature before, # we simply append the current string to that existing group natively." if key in hm: hm[key].append(s) # "Otherwise, this is a new anagram group, so we initialize it." else: hm[key] = [s] # "Finally, our dictionary has grouped everything perfectly without any overhead. # I can just extract the values and return them." return list(hm.values())