Problem:
Given a list of words , group anagrams together and create a list of anagram lists.
Example:
For the input :
["eat","tea","tan","ate","nat","bat"] The output is :
[ [“eat”,”tea”,”ate”],[“tan”,”nat”],[“bat”]]
Assumptions:
- the letters are in lowercase English
- the order of the words in the anagram list doesn’t matter
Try out the solution here:
https://leetcode.com/problems/group-anagrams/
Solution:
Hint:
- Use a hash map to group all anagrams together
ALGORITHM:
STEP 1: Create a map to store group of anagrams together
STEP 2: For every word , sort the letters in the word and use it as a key in the hash map. Add the original word to a list and store it in the map. For every word , compute the key this way and keep adding anagram words to the respective list.
STEP 3: Convert the map values to a list and return
Code:
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
var map = new HashMap<String,List<String>>();
for(int i=0;i<strs.length ;i++){
char[] a = strs[i].toCharArray();
Arrays.sort(a);
String s = new String(a);
if(!map.containsKey(s)){
var list = new ArrayList<String>();
list.add(strs[i]);
map.put(s,list);
}else{
var list = map.get(s);
list.add(strs[i]);
map.put(s,list);
}
}
var finalList = new ArrayList<List<String>>(map.values());
return finalList;
}
}
Time complexity of above algorithm is O(m*nlogn) where m is the number of words in the input and n is the maximum number of characters in a word.
Space complexity is O(m*n)
The time complexity can be further reduced if instead of sorting the letters in each word and using it as a key in the output map , we could find the frequency of characters in each word and store it in their respective indices in a character array and then use that as a key.
If you had noticed , one of the assumptions say the characters are all lower case English letters.
So we need a array of size 26 to store the frequency.
You could use an int array or char array for the same.
Since char array occupies less memory (0 to 127 characters) we can prefer char array.
Here is the refactored code:
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
var map = new HashMap<String,List<String>>();
for(int i=0;i<strs.length ;i++){
char[] freq = new char[26];
for(char c:strs[i].toCharArray()){
freq[c -'a']++;
}
String frequency = String.valueOf(freq);
if(!map.containsKey(frequency)){
var list = new ArrayList<String>();
list.add(strs[i]);
map.put(frequency,list);
}else{
var list = map.get(frequency);
list.add(strs[i]);
map.put(frequency,list);
}
}
var finalList = new ArrayList<List<String>>(map.values());
return finalList;
}
}
The time complexity is now reduced to O(m * n ) since the time complexity for sorting nlogn is not required.
Space complexity remains the same.
That’s it!
Leave a Reply