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.\n\n- Constraints:\n - 1 <= strs.length <= 10^4\n - 0 <= strs[i].length <= 100\n - strs[i] consists of lowercase English letters.\n- Example:\n \n Input: strs = ["eat","tea","tan","ate","nat","bat"]\n Output: [["bat"],["nat","tan"],["ate","eat","tea"]]\n \n (Order of inner lists and strings within inner lists doesn't matter)

Solution

  • Approach:\n - The key idea is that anagrams become identical when sorted alphabetically.\n - We can use a hash map (or dictionary) where the key is the sorted version of a word, and the value is a list of all original words that, when sorted, produce that key.\n - Iterate through each word in the input array.\n - For each word, sort its characters to create a canonical key.\n - Add the original word to the list associated with this sorted key in the hash map.\n - Finally, the result will be all the values (lists of words) from the hash map.\n\npython\nimport collections\n\nclass Solution:\n def groupAnagrams(self, strs: list[str]) -> list[list[str]]:\n # Use a defaultdict to automatically create a list for new keys\n # if the key doesn't exist.\n anagram_groups = collections.defaultdict(list)\n\n for s in strs:\n # Sort the string to create a canonical key.\n # 'sorted(s)' returns a list of characters, join them back to a string.\n sorted_s = "".join(sorted(s))\n # Add the original string to the list associated with its sorted key.\n anagram_groups[sorted_s].append(s)\n\n # The result is all the values (lists of anagrams) from the dictionary.\n return list(anagram_groups.values())\n