[[Hasmaps and hash sets]]

Problem

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

Example 1:

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

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

Explanation:

• There is no string in strs that can be rearranged to form "bat".
• The strings "nat" and "tan" are anagrams as they can be rearranged to form each other.
• The strings "ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.

Example 2:

Input: strs = [""]

Output: [[""]]

Example 3:

Input: strs = ["a"]

Output: [["a"]]

Brain storming

The key here is to create a canonical key of sorted alphabets . For example see “eat” , “tea” if we sort them alphabetically they will become “aet” , “aet” this is the key for which we can create a hashtable ( dictionary) with this key and all the words that have this key will fall into its values

anagrams = {"aet":["aet","eat", "tea"],

"ant": ["tan", "nat"], "abt" : ["bat"]}

So the candidate needs to make the function “create_canoncial_key” that takes in the word and make a key for it

def create_canonical_key(word):

return "".join(sorted([char for char in word]))

Then in the main loop we check if for the new word do we have the key for it already part of this anagrams dict or not if not make the entry else append the word in the values list

for word in words:
	key = create_canonical_key(word)
	if key in anagrams:
	  anagrams[key].append(word)
	else:
	  anagrams[key] = [word]

final version

from collections import defaultdict

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

anagrams = defaultdict(list)

def create_canonical_key(word:str) -> str:
	return "".join(sorted(word))

def group_anagrams(strs:list[str]) -> list[str]:
	for word in strs:
		key = create_canonical_key(word)
		anagrams[key].append(word) # the default dict will make sure that if the key is not present then it makes an empty list and if the key is present then it adds the word to its existing list
	return sorted([sorted(group) for group in anagrams.values()])