Leetcode Problem: Group Anagrams
Objective:
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.
Pattern: Arrays and Hashing
Approach:
- Create a 2D list for the result.
- Create a HashMap: key = sorted word, value = list of anagrams.
- Iterate through the input string array and sort the input.
- If the sorted input is not in hashmap or edge case where the sorted input equals the non-sorted input then add the sorted input as the key and the non-sorted input as an anagram.
- If the sorted input already exists as a key in the hashmap, then get the sorted key and add the non-sorted input into the anagram list.
- Iterate through the hashmap and add each anagram list into the result list. Return result.
Big-O Notation:
Time Complexity: O(m * nlog(n))
We have iterate n times for each string.
We sort each string using Arrays.sort() which is O(n log(n)).
Space Complexity: O(n * m)
We use additional data structures for storage.
We have a 2D list to store the result.
We have a hashmap to store elements.
Code:
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
// input: string array
// output: 2D list
List<List<String>> result = new ArrayList<List<String>>();
Map <String, List<String>> hashMap = new HashMap<>();
for(String str : strs){
char [] array = str.toCharArray();
Arrays.sort(array);
String sortStr = str.valueOf(array);
// edge case if current == key then add to key.
if(sortStr == str || !hashMap.containsKey(sortStr)){
List <String> anagram = new ArrayList<>();
anagram.add(str);
hashMap.put(sortStr, anagram);
} else {
hashMap.get(sortStr).add(str);
}
}
// add anagram list into result
for(String s : hashMap.keySet()){
result.add(hashMap.get(s));
}
return result;
}
}
Top comments (0)