Leetcode 49 - Group Anagrams
Leetcode Link for Group Anagram
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.
Solution:
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> map = new HashMap<>();
for(String str: strs){
char ch[] = str.toCharArray();
Arrays.sort(ch);
String key = new String(ch);
map.computeIfAbsent(key, l -> new ArrayList<>()).add(str);
}
return new ArrayList<>(map.values());
}
Github Link: https://github.com/miqbal3636/problem_solving/blob/main/src/com/spsoft/leetcode/medium/hashmap/L49AnagramGrouper.java
Explanation:
-
Create a HashMap: A Map<String, List
> named map is initialized to store lists of anagrams, where the key is the sorted version of the string, and the value is a list of strings that are anagrams of each other. -
Iterate over Strings: For each string in the input array strs, the following steps are performed:
-
Convert the string into a character array.
-
Sort the character array.
-
Convert the sorted character array back into a string, which serves as the key.
-
Group Anagrams: Using map.computeIfAbsent, check if the key exists in the map. If it doesn’t, a new ArrayList is created and associated with the key. The original string is then added to the list associated with that key.
-
Return Result: Finally, return a list of all the grouped anagrams by creating a new ArrayList from the values of the map.
This method ensures that all strings that are anagrams of each other are grouped together in the result. The sorted version of the string acts as a unique identifier for anagrams.
Time Complexity: Iterating through Strings:
-
The loop iterates through each string in the array strs. This takes 𝑂(𝑛)time, where 𝑛 is the number of strings in the array.
-
Sorting Each String:
-
For each string, converting it to a character array and sorting it takes 𝑂(𝑚log𝑚) time, where 𝑚 is the maximum length of the strings. Since the sorting operation is done for each string, this step takes 𝑂(𝑛 ⋅ 𝑚log𝑚) time overall.
-
Creating/Updating the HashMap: In the worst case, the time complexity for inserting or updating a value in the HashMap is 𝑂(1) (amortized constant time).
Overall Time Complexity: Combining these, the overall time complexity is: 𝑂(𝑛 ⋅ 𝑚log𝑚)
Space Complexity:
-
Space for the HashMap: In the worst case, the HashMap will store all the strings grouped by their sorted character key. This takes 𝑂(𝑛 ⋅ 𝑚) space, where 𝑛 is the number of strings and 𝑚 is the maximum length of the strings.
-
Space for the Sorted Character Arrays: The character array and the sorted character string for each string also take 𝑂(𝑚) space. Since this is done for each string, it contributes 𝑂(𝑛 ⋅ 𝑚) space.
Overall Space Complexity: Combining these, the overall space complexity is 𝑂(𝑛 ⋅ 𝑚)
| Complexity Type | Value |
|---|---|
| Time Complexity | O(n . m logm) |
| Space Complexity | O(n . m) |
Author: Mohammad J Iqbal
