Given an array of strings strs, group the anagrams together. You can return the answer in any order.
LeetCode Solutions"bat"."nat" and "tan" are anagrams as they can be rearranged to form each other."ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.1 <= strs.length <= 1040 <= strs[i].length <= 100strs[i] consists of lowercase English letters.Where m is the number of strings in the input array and n is the maximum length of a string. Sorting each string takes time, and we do this for all m strings.
In the worst case, all strings are anagrams of each other, and we store all n strings in a single group. The space required for the hash map is due to storing the sorted keys and the original strings.
In this approach, we use a hash map (or dictionary) to group the anagrams together. The key for the hash map is generated by sorting the characters of each string. Since anagrams will have the same sorted character sequence, they will be grouped under the same key in the hash map. After processing all strings, we return the values of the hash map, which are the groups of anagrams.
Where m is the number of strings in the input array and n is the maximum length of a string. For each string, we iterate through all its characters once to build the count array, which takes time. We do this for all m strings.
In the worst case, all strings are anagrams of each other, and we store all n strings in a single group. The space required for the hash map is due to storing the count arrays and the original strings.
In this approach, instead of sorting the strings, we create a count array for each string that counts the occurrences of each character (assuming only lowercase English letters). The count array is then used as a key in the hash map to group anagrams together. Since anagrams will have the same character counts, they will be grouped under the same key in the hash map. After processing all strings, we return the values of the hash map, which are the groups of anagrams.
| Approach | Rating | Time Complexity | Space Complexity | Advantages | Disadvantages |
|---|---|---|---|---|---|
| Sorting Each String | Simple to understand and implement, works for any character set | Slower due to sorting overhead per string | |||
| Character Count Array (Optimized Hash Map) | More efficient with linear time complexity per string, avoids sorting overhead | Only works when the character set is known and limited |
The optimal approach for this problem is Solution 2: Character Count Array (Optimized Hash Map), which achieves time complexity by using a fixed-size array of 26 elements as a hash key instead of sorting. This approach is most suitable when dealing with strings that contain only lowercase English letters, as it avoids the sorting overhead per string and directly uses character frequency counts for grouping.
class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: # Create a dictionary to hold the groups of anagrams dict = defaultdict(list)
for s in strs: # Sort the string to get the key for the anagram group, E.g., "eat" -> "aet" sorted_s = "".join(sorted(s)) dict[sorted_s].append(s)
return list(dict.values())class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: # Create a dictionary to hold the groups of anagrams dict = defaultdict(list)
for s in strs: counts = [0] * 26 # Initialize a count array for each character
for char in s: counts[ord(char) - ord('a')] += 1 # Increment the count for this character
dict[tuple(counts)].append(s) # Use the count array as a key to group anagrams
return list(dict.values())