Algorithms for Coding Interviews in Python/

...

/

Solution: Group Anagrams

Solution: Group Anagrams

Here's a detailed analysis on how to solve the Group Anagrams problem.

We'll cover the following...

Solution: using dictionary and list

Python 3.5
def anagrams(lst):
    """
    Function to find anagram pairs
    :param lst: A lst of strings
    :return: Group of anagrams
    """
    
    # Empty dictionary which holds subsets of all anagrams together
    dictionary = {}
    # traversing all the lst strings
    for string in lst:
        # sorting the lst string and storing it in a key
        key = ''.join(sorted(string))
        # if the key is already in the dictionary then appending the original lst(Anagram).
        if key in dictionary.keys():
            dictionary[key].append(string)
            
        else:  # If there is no key in the dictionary
            dictionary[key] = []
            dictionary[key].append(string)
    # traversing the whole dictionary and concatenating values and keys
    result = []
    for key, value in dictionary.items():
        if len(value) >= 2:
            result.append(value)
    result = sorted(result) # sort the list
    return result
# Driver to test above code
if __name__ == '__main__':
    lst = ['tom marvolo riddle ', 'abc', 'def', 'cab', 'fed', 'clint eastwood ', 'i am lord voldemort', 'elvis', 'old west action', 'lives']
    print (anagrams(lst))

Explanation

This solution sorts each input string in an ascending order, considers it as a key and the original string as the value of the corresponding key. It then checks if the key exists in a dictionary or not. If it doesn’t exist, it means it is occurring for the very first time, so it maps an empty list to the key and appends a value in it. If the key is already present, it simply appends the value to the list.

Now, each list in the dictionary has anagrams. In the end, it iterates over the dictionary and stores all the values in a list if, in the key-value pair, the value corresponding to the key is greater than 2. The resultant list is returned, which has the pair of anagrams.

Time complexity

Sorting one ...