Group Anagrams

Tags:

Many a times we need to sort some things which are not integers, foremost being strings. How do we go about using quicksort? I did not know that the C library has a function for it. This function is very powerful and easily sort anything given the compare function. So in today’s post, we will be using that function and learn how it can be used to solve our problem statement.

Given a list of words, group all words together which are anagrams. For example, if the input is like :

cat tac act dog god gdo

First of all, we want to understand how to strings can be identified as anagrams. There are more efficient ways to do it, but the most simple one is sort two string based on characters and if two resultant strings match, two strings are anagrams.
Now the problem boils down to sorting each individual string and then sort the entire array of strings. The anagram strings will automatically grouped together.
If we look closely, we have another problem, that is when we sort the original strings individually, original strings are lost. So, idea is to have a duplicate array of strings and then sorting operation. Also to after sorting the duplicate array, we will lose the original index of string once we sort the entire array. Hence we need to store that information too. Let’s figure what we need to store and how? We have array of strings, let’s say there can be a maximum 100 such strings. So we create an array of character pointers to store these strings. Also, we need a duplicate array where we will sort strings and also we need to store the position of the string in original array so, the duplicate array would look like:
Next step is to sort individual string in the duplicate array, where we will use the library function qsort().
This function is very easy to use, there are four parameters you have to pass:
1. The buffer or the array you want to have sorting performed on.
2. The size of the buffer
3. Size of an individual element of the buffer.
4. And last and most important is the compare function, which has to be written in code and passed as function pointer to this function. For further details of qsort() function usage follow : qsort
Once all the strings are individually sorted, sort the entire array of strings using the same qsort(), only difference will be the compare function which will now run on an entire string instead of character. We are almost done! Now we have all anagrams placed next to each other, however, we need to print original words. That’s where the index we stored in duplicate array will help and we will print words from original array using the order given in the duplicate array.

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        
        Map<String, List<String>> map = new HashMap<>();
        
        for(int i=0; i < strs.length; i++){
            char [] temp = strs[i].toCharArray();
            Arrays.sort(temp);
            
            String keyString  = String.valueOf(temp);
            
            if(!map.containsKey(keyString)){
                map.put(keyString, new ArrayList<>());
            }
            map.get(keyString).add(strs[i]);
        }
        
        return new ArrayList<List<String>>(map.values());
    }
}

This code will perform sorting on M strings, each of size N characters, so the complexity of the algorithm to print all anagrams together will be O(MlogM + MNlogN) MNlogN because NlogN for sorting each string of size N and there are M strings, MlogM to sort M strings in the array.