49. Group Anagrams

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

    word_dict = {}

    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):

1. Initialize a Dictionary: Create an empty dictionary.
2. Iterate Through the List of Strings: Loop through each string in the input list.
3. Sort Each String and Convert to a Tuple: For each string, sort the characters and convert the sorted list to a tuple.
4. 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.
5. Return the Values of the Dictionary: Extract the values from the dictionary which are the groups of anagrams.

from collections import defaultdict

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.