LeetCode #49 — Group Anagrams (Python)

Problem

Given an array of strings, group anagrams together.

Example

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Conditions

• All inputs will be in lowercase.
• The order of your output does not matter.

Approach

Time Complexity — O(n*len(array item))

Space Complexity — O(n)

This question involves the need to compare check whether each item in the array is an anagram of a previously read item. The approach to this question is quite straight forward — if the current item being read is an anagram of an item previously read, put them in the same array. If not, put it in a new array.

To keep track of this, we will be using a dictionary — denoted by var ‘d’

‘’.join(sorted(strs[i])) — sorts each character in the string and rearranges them in lexicographic-ally (i.e. bga → abg)

after this, the we then check whether the sorted string (x) is an existing key in the dictionary, if so — append the original string to the array stored under the key in the dictionary. Else — create a new key in the dictionary with the sorted string as a key + append the original string (in an array) as a value.

* Note: The reason the original string is appended as an array is to ensure that should subsequent anagrams be added under this key in the dictionary, this would allow for us to conveniently store additional strings

I really hope someone found this helpful in some way or another. This probably isn’t the cleanest approach (code wise) to this question but the idea is there. Please leave a comment if there’s anything which needs clarification!