Data Structures & Algorithms in Java – Strings – Group Anagrams

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/

Advertisements

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)

Advertisements

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

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s