Topic: Arrays & Hashing
Soln 1 (dictionary):
create a dictionary
iterate through the string of wordsa
sort the word alphabetically
if the key[sorted word] is not in the dictionary then add it and use the original word as its value
else append the word to the already existing key
for word in strs:
sorted_word = ”.join(sorted(word))
if sorted_word not in word_dict:
word_dict[sorted_word] = [word]
else:
word_dict[sorted_word].append(word)
return list(word_dict.values())
Soln 2 (tuples + defaultdict):
Initialize a Dictionary: Create an empty dictionary.
Iterate Through the List of Strings: Loop through each string in the input list.
Sort Each String and Convert to a Tuple: For each string, sort the characters and convert the sorted list to a tuple.
Use Tuple as Key and Append String as Value: Use the tuple as the key in the dictionary. Append the original string to the list corresponding to this key.
Return the Values of the Dictionary: Extract the values from the dictionary which are the groups of anagrams.
def group_anagrams(strs):
count = defaultdict(list)
for i in strs:
count[tuple(sorted(i))].append(i)
return count.values()
Note: defaultdict is a sub-class of the dictionary class that returns a dictionary-like object. The functionality of both dictionaries and defaultdict are almost same except for the fact that defaultdict never raises a KeyError. It provides a default value for the key that does not exists.
Tuple is an ordered, immutable collection of elements.
