Python Solution:

49. Group Anagrams

Solved

Medium

Topics

Companies

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.

Example 1:

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

Example 2:

Input: strs = [""] Output: [[""]]

Example 3:

Input: strs = ["a"] Output: [["a"]]

Constraints:

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

Understand:

- We need to return a list of lists that has anagrams for each list.

Example Result 1: [["bat", "tab"], ["banana"], ["ate", "tea", "eat"]]
Example Result 2: [[dab, bad], [car, arc], [asdf, fdsa, sdfa]]

Match:

If following along neetcode.io in order, we see this as a step above "242 Valid Anagram" problem

Plan:

For the most efficient solution:
- We use "bat" as our example
Note: We convert letter to ASCII value here so we can store to correct count index

"b" in "bat" would put index as:

count[2] += 1

"a" in "bat" would put index as:

count[1] += 1

Again but we use "tab" as our example. We break it down into smaller steps for more clarity.

Implement:

def groupAnagrams():
	ans = collections.defaultdict(list)
	
	for s in strs:
		count = [] * 26
		for c in s:
			count[ord(c) - ord("a")] += 1
			ans[set(count)].append()
	return ans

Result:

Here's another another image of the result for clarity: groupAnagramsResult

Evaluate:

The brute force method suggests that we loop through strs
- Sort each string as sortedStr
- So that we have sortedStr as a key and implement the list values the same way
  - Resulting in O(m*nlogn) where
    - nlogn is sorting time for each m string we pass through
The solution we showed indicates that we
- loop through strs
  - loop through and count each letter and set as unique key in a countList
- We evaluate the efficient solution as O(m * n) which is faster than O(m *n * logn)

C# Solution: