back

Group Anagrams

tags: Leetcode, Medium, Arrays and Hashing

Python Code

"""
Approach: Arrays and Hashing
Time Complexity: O(N.K)
Space Complexity: O(N.K)
"""

from collections import defaultdict
from typing import List


class GroupAnagrams:
    def _group_anagrams(self, strs: List[str]) -> List[List[str]]:
        # initialize a result hash to have values as list
        result_hash = defaultdict(list)
        # iterate through every word in the input list
        for word in strs:
            # for every work initialize a freq list to hold 26 values (one for each letter of the alphabet) with initial
            # value as 0
            freq = [0] * 26
            # iterate through every character of the word
            for char in word:
                # increment corresponding index value of that character by one
                freq[ord(char) - ord('a')] += 1
            # convert the frequency list to a tuple and append the word to the list in the hash
            result_hash[tuple(freq)].append(word)
        # return all the values of the result_hash
        return result_hash.values()

    def process(self, input_list: List[str]) -> None:
        print(f"\nOutput >> {self._group_anagrams(input_list)}\n")


if __name__ == '__main__':
    input_string_list = []
    count = int(input("Enter the number of words in the input list: "))
    print("Enter the words: ")
    for _ in range(count):
        input_string_list.append(input())
    GroupAnagrams().process(input_string_list)

Output

/usr/bin/python3 /Users/vinoddalavai/Dev/group_anagrams.py 
Enter the number of words in the input list: 6
Enter the words: 
eat
tea
tan
ate
nat
bat

Output >> dict_values([['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']])


Process finished with exit code 0