mediumHashingPattern: Hashing + Sorting
Group Anagrams Solution
Problem Statement
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.
Examples
Example 1:
Input:["eat","tea","tan","ate","nat","bat"]
Output:[["eat","tea","ate"],["tan","nat"],["bat"]]
Explanation: The groups are ["eat", "tea", "ate"], ["tan", "nat"], and ["bat"], each of which contains strings that are anagrams of each other.
Example 2:
Input:["a"]
Output:[["a"]]
Explanation: The only group is ["a"].
Example 3:
Input:[""]
Output:[[""]]
Explanation: The only group is [""] (empty string).
Constraints
- 1 <= strs.length <= 10^4
- 0 <= strs[i].length <= 100
- strs[i] consists of lowercase English letters.
- Each string strs[i] is unique in its original input array (as per problem statement, although anagrams are allowed within groups).
- The total number of characters across all strings will not exceed 10^5.
Time: O(N * K log K) Space: O(N * K)
The optimal approach involves using a hash map. Iterate through the input array of strings. For each string, create a canonical representation (either by sorting its characters or by creating a frequency count of its characters). Use this canonical representation as the key in a hash map. The value associated with each key will be a list of all original strings that map to that canonical representation. Finally, collect all the lists from the hash map's values.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def group_anagrams(strs):
anagram_map = {}
for s in strs:
sorted_s = ''.join(sorted(s))
if sorted_s not in anagram_map:
anagram_map[sorted_s] = []
anagram_map[sorted_s].append(s)
return list(anagram_map.values())