Question

Answer the 2 questions below related to this function.

# words is a list of strings.

# This function returns the list of all groups of anagrams.

# Sample input: ["yo", "act", "flop", "tac", "cat", "oy", "olfp"]

# Sample output: [["yo", "oy"], ["flop", "olfp"], ["act", "tac", "cat"]]

def groupAnagrams(words):
   anag = {}
   for word in words:
       table = [0] * 128
       for ch in word:
           table[ord(ch)] += 1
       aKey = tuple(table)
       if aKey not in anag:
           anag[aKey] = [word]
       else:
           anag[aKey].append(word)
   return list(anag.values())

1) I think the time complexity is O(w * s) where w is the length of words and s is the length of the longest string in the list words. Also, I think the space complexity is O(w) because in the worst case the dictionary anag will have w keys. Note that the list table has a constant length of 128 (represents the ascii table). Am I wrong and if yes, how?

2) Is there a better way to do this? What would be a more efficient solution?

Answer 1

Q->1:  I think the time complexity is O(w * s) where w is the length of words and s is the length of the longest string in the list words. Also, I think the space complexity is O(w) because in the worst case the dictionary anag will have w keys. Note that the list table has a constant length of 128 (represents the ascii table). Am I wrong and if yes, how?

Answer:

You are right actually., But your explanation of space complexity is little misleading,

Space complexity is O(w) because in dictionary there will be a total of w words in the values.

Q->2: Is there a better way to do this? What would be a more efficient solution?

Answer:

No, actually there is no better way to do this.