49_Group Anagrams

Level: medium

Tag: string, hash table

Question

Given an array of strings, group anagrams together.

Example:
Given: ["eat", "tea", "tan", "ate", "nat", "bat"], 
Return:
[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note: All inputs will be in lower-case.

Idea

1. With sort. Create a dictionary to store sorted non-duplicated elements as keys, and corresponding items in the strs list as values. Keys should be tuple, because tuple is immutable but list is mutable. After sorting a string, the result is a list. So we need to transfer the list to tuple. Values are stored in list.

2. Without sort, use count table. Create a dictionary to store count table as keys, corresponding items in the strs list as values. We need to transfer the count table to tuple as well.

Complexity 1 (with sort)

• Time Complexity: $O(nklogk)$ , where n is the length of strs, and k is the maximum length of a string in strs. The outer loop has complexity $O(n)$ as we iterate through each string. Then, we sort each string in $O(klogk)$ time.
• Space Complexity: $O(nk)$ , the total information content stored inans.

Complexity 2 (without sort, use count table)

• Time Complexity: $O(nk)$ , where n is the length ofstrs, and k is the maximum length of a string instrs. Counting each string is linear in the size of the string, and we count every string.
• Space Complexity: $O(nk)$ , the total information content stored inans.

Solution 1 (with sort)

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """

        dic = {}

        for item in strs:
            sortedItem = tuple(sorted(item))   # must use tuple instead of list as output of sorted()
            if dic.get(sortedItem) == None :
             dic[sortedItem] = [item]          # set up type of dic.values as list before append elements
            else :
             dic[sortedItem].append(item)           
        return dic.values()

Solution 2 (without sort, use count table)

    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """

        dic = {}

        for item in strs :
            countTable = [0]*26     # create count table to store frequency of 26 letters
            for letter in item :
                countTable[ord(letter) - ord("a")] += 1   # count frequency for each item in strs
            if dic.get(tuple(countTable)) == None :
                dic[tuple(countTable)] = [item]
            else :
                dic[tuple(countTable)].append(item)
        return dic.values()