LeetCode 49. Group Anagrams — Python Programming Solution

Blind 75 — Programming & Technical Interview Questions — Explanation Series

The Problem:

Given an array of strings “strs”, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

The Constraints:

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.

The Explanation:

To solve this problem the first thing you have to recognize is that all anagrams are the same length and made up of the same letters in different orders. Therefore your next thought should be “How do I reorder the letters so that I know a word is an anagram of another?” In Python this is easy to do, just sort the characters in the string by alphabetical order. Now all you have to do is go through all the sorted strings and add the original string. The greedy solution would be 2 for loops and just check every string against the other, but you should usually assume there is a better option than that. In this case you can use a Python dictionary where the keys are the sorted strings and the value is a list of all the original strings that when sorted are the key. This allows you to complete this problem in 1 pass O(n) time and complexity.

The Python Programming Solution:

This solution uses a few Python tricks you just need to know. First, we use a defaultdict instead of a regular dictionary because defaultdicts allow you to specify the default value when a key has no value. In this case we specify a list since we will be returning a list of lists. Then when sorting a string Python turns it into a list of characters in alphabetical order. Join all these characters on an empty string to get them back into string form. Append the original string to the list (thanks to our default dict) where the key is the sorted string. Lastly, take all of the values of sMap, convert them into a list, and return.

class Solution:
  def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
    sMap = defaultdict(list)

    for s in strs:
      sorted_s = "".join(sorted(s))
      sMap[sorted_s].append(s)
    
    return list(sMap.values())

Congratulations! You now know how to solve Leetcode 49. Group Anagrams. This is a LeetCode easy but helps as a base for the more comples problems. Please check out my page for more LeetCode solutions and machine learning articles or check out my twitter!

Information:

Medium: medium.com/@nkwade
Website: nkwade.dev
LinkedIn: linkedin.com/in/nkwade
GitHub: github.com/nkwade
Email: nicholas@nkwade.dev
Twitter: twitter.com/nkwade_world