< Back




49. Group Anagrams

More interesting hashing example. Basically we have a list of strings, return a list of lists that
groups strings based on whether or not they are anagrams of each other.

The most inefficient way to do this would be to compare each string to every other string, this will
end up with a time complexity of O(n^2 * m) - definitely not optimal.

We've got two ways to solve this in a faster time. We can create a dictionary where the keys are
sorted versions of the input strings - effectively creating a hash for an anagram-able string. We
would have to sort every string provided to us in the list, and then were can find its home in the
dictionary. This would give us a time complexity of O(n * mlogm).

The cooler way to solve this is to create a dictionary where the keys are a tuple with the count of
each character in the string. This would give us a time complexity of O(n * m).

The solution is as follows:


  class Solution:
      def groupAnagrams(self, strs):
          ans = collections.defaultdict(list)
          for s in strs:
              count = [0] * 26
              for c in s:
                  count[ord(c) - ord('a')] += 1
              ans[tuple(count)].append(s)
          return ans.values()


_ Time Complexity:

  O(n * m) - We iterate through each string in the input list and count the occurrences of each
  character in the string.

_ Space Complexity:

  O(n * m) - We store a list of lists of strings in the answer variable.