Group Anagrams
Problem Description
Question
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"]]
Constraints:
- 1 <= strs.length <= 104
- 0 <= strs[i].length <= 100
strs[i]consists of lowercase English letters.
Solve it on LeetCode
Approaches
1. Sorting Each Word
Intuition:
The first idea is to use the property that if two strings are anagrams of each other, their sorted form will be the same. By sorting each string and using it as a key, we can group the words that are anagrams together.
- Iterate over the list of strings.
- Sort each string and use it as a key in a hashmap where the value will be a list of strings.
- Finally, return all the values of the hashmap that represent grouped anagrams.
Code:
Complexity Analysis
- Time Complexity: O(NK log K) where N is the number of strings and K is the maximum length of a string. Sorting each string takes O(K log K).
- Space Complexity: O(NK), the space for storing the groups of anagrams.
2. Counting Characters
Intuition:
Instead of sorting, we can use the frequency of characters as a key. If two strings are anagrams, they will have the same frequency distribution of characters.
- Use an array of size 26 to count the frequency of each character for each string because all characters are lowercase.
- Convert this frequency array to a unique string and use it as a key in a hashmap.
- Group strings with the same frequency distribution together.
Code:
Complexity Analysis
- Time Complexity: O(N * K), as constructing the unique string key per word from its character count takes O(K).
- Space Complexity: O(N *K), storing the groups of anagrams based on their character frequency in the hashmap.