Anagram Groups [Solution]
This exercise assesses your ability to work with strings, dictionaries, and lists. It also evaluates your understanding of anagrams and your problem-solving skills.
Below is a Python implementation of the group_anagrams function to group a list of strings into sets of anagrams:
from typing import List
def group_anagrams(strings: List[str]) -> List[List[str]]:
anagram_groups = {} # Dictionary to store groups of anagrams
for string in strings:
# Sort the characters in the string to identify its anagram group
sorted_string = "".join(sorted(string))
# If the sorted string is not in the dictionary, add it with an empty list
if sorted_string not in anagram_groups:
anagram_groups[sorted_string] = []
# Add the original string to its anagram group
anagram_groups[sorted_string].append(string)
# Convert the dictionary values to a list to get the final result
result = list(anagram_groups.values())
return result
# Example usage:
input_strings = ["listen", "silent", "enlist", "heart", "earth", "night", "thing"]
result = group_anagrams(input_strings)
print(result)
Time Complexity:
This solution uses a dictionary to group strings based on their sorted versions,
which allows for efficient grouping of anagrams.
The time complexity is O(n * k * log(k))
, where n
is the number of strings and
k
is the maximum length of a string.
Space Complexity:
The space complexity is O(n)
as we store the anagram groups in a dictionary.