What’s New ?

The Top 10 favtutor Features You Might Have Overlooked

Read More

Group Anagrams (With Java, C++ and Python Solution)

  • Mar 12, 2022
  • 7 Minutes Read
Group Anagrams (With Java, C++ and Python Solution)

 

Group anagrams is one of the commonly asked interview questions to test your knowledge about data structure and problem-solving ability. Even though the problem's solution is pretty easy, students mostly fail to solve it with the correct approach. Therefore, before coding the problem's solution, let us first understand the problem statement and detailed approach to solve it.

What is Group Anagrams Problem?

You can define an anagram as rearranging the letters of a different word or phrase by using all the original letters exactly once. Similarly, in this problem, you are given an array of strings and you have to group all the anagrams together. 

For example: if the array is {"eat", "bat", "ate"}, the output of the problem will be [["bat"], ["ate", "eat"]].

As you are given the list of some strings and you have to find anagrams, there is a possibility that you do not find any group of anagrams. It is possible that it can exists as an individual group and you can return that group in any order. 

Solution of Group Anagrams Problem

Generally, when you understand the concept of the problem, the first approach that comes to your mind is to solve it using the brute force approach. Let us understand it in detail below.

Method 1: Brute Force Approach

Using the brute force approach, you can iterate through the list of words and search for the anagram for each word maintaining the array to avoid duplicates.

You can also count the number of characters of two strings, and if they match, they are anagrams of each other. For example, if the two same strings are ‘bca’ and ‘cab,’ then you can count the characters like {a:1, b:1, c:1}.

Using this approach is not effective enough as you cannot get the optimal solution. Therefore, to find the optimal solution to the problem, you can use the sorting technique and dictionary data type. Wondering how? Let's understand it in detail below

Method 2: Optimal Solution

If you have two strings that are an anagram of each other, sorting those strings will give you the same string as the output. For example, if the strings are ‘bac’ and ‘cab,’ sorting these two strings will result in output as ‘abc.’ Therefore, you can conclude that the strings are anagrams of each other.

You can use a dictionary as a data type to effectively store the outputs of the strings and anagrams.

Algorithm

1. First, initialize the empty map, which can store the sorted string and compare them to find the anagram of the given words.
2. Then for every string of the list, sort the string using a sorting algorithm.
3. If there exists an entry in the map for the given string, add the current string to the list.
4. Create a new list with the elements and add it to the map
5. Lastly, return the list of all values in the map

 

Check out the below coding solutions for a better understanding 

Python Code for Group Anagrams

class Solve():
   def Anagrams( self, li ):
       '''
       Function to Group Anagrams
       :param li: list of words
       :return: list of grouped anagrams
       '''
       dictionary = {}
       for word in li:
           sortedWord = ''.join(sorted(word))
           # If word is not in dictionary
           if sortedWord not in dictionary:
               dictionary[sortedWord] = [word]
           # If previously it is present that means its anagram
           # was previously present
           else:
               dictionary[sortedWord] += [word]
       return [dictionary[i] for i in dictionary]

if __name__ == '__main__':
   li = ['pop','bat','tab','opp']
   # Call to function to Solve and group Anagrams
   print(Solve().Anagrams(li))

 

Java Code for Group Anagrams

public class ft {
    public static List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<>();
        HashMap<String, List<String>> map = new HashMap<>();
        for(int i=0;i<strs.length;i++){
            char str[] = strs[i].toCharArray();
            // sort string
            Arrays.sort(str);
            String s = String.valueOf(str);
            if(map.get(s)!=null){
                List<String> a = map.get(s);
                a.add(strs[i]);
                map.put(s, a);
            }
            else{
                List<String> a = new ArrayList<>();
                a.add(strs[i]);
                map.put(s, a);
            }
        }
        for(Map.Entry<String, List<String>> en:map.entrySet()){
            res.add(en.getValue());
        }
        return res;
    }
    public static void main (String[] args) throws java.lang.Exception
    {
        String[] words = {"pop","bat","tab","opp"};
        List<List<String>> res = groupAnagrams(words);
        System.out.println(res);
    }

}

 

C++ Code for Group Anagrams

#include<bits/stdc++.h>
#include
using namespace std;
class Solution {
public:
    /* Utility to check if word is palindrome*/
    bool isPal(string s){
        int i=0,j=s.length()-1;
        while(i<=j){
            if(s[i]!=s[j]){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
    vector<vector<int>> palindromePairs(vector<string>& words) {
        unordered_map<string,int>mp;
        vector<vector<int>>v;
        for(int i=0;i<words.size();i++){
            mp[words[i]]=i;
        }
        for(int i=0;i<words.size();i++){
            for(int j=0;j<=words[i].size();j++){
                string prefix=words[i].substr(0,j);
                string suffix=words[i].substr(j);
                if(isPal(prefix)){
                    string rev=suffix;
                    reverse(rev.begin(),rev.end());
                    if(mp.count(rev) && mp[rev]!=i){
                        v.push_back({mp[rev],i});
                    }
                }
                 if(isPal(suffix)){
                    string rev=prefix;
                    reverse(rev.begin(),rev.end());
                    if(mp.count(rev) && mp[rev]!=i && !suffix.empty()){
                        v.push_back({i,mp[rev]});
                    }
                }
            }
        }
        return v;
    }
};
int main(){
    vector<string> s = {"pa","a","tot","","anagram","cpp","p"};
    vector<vector<int>> v = Solution().palindromePairs(s);
    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v[i].size(); j++)
            cout << v[i][j] << " ";
        cout << endl;
    }
    }

 

Time Complexity

The running time complexity of the problem turns out to be O(nm), where n is the number of strings in the list and m is the average length of the strings in the list.

Example

If you consider the input array of strings as

Group anagrams example

The array after sorting the element will result as shown below

Hence, the final output based on the sorting of the strings will be

Conclusion

Testing the understanding of the data structure of the candidate is one of the main priorities for any interviewer. Group anagram is one of the problems which can help the interviewers to target their goals and therefore it is necessary to learn and understand the problem thoroughly. This article includes different approaches to solve group anagrams problems and its coding solution in python, java, and c++ programming language.

If you still find any difficult to solve the problem, please get in touch with our Live coding tutors with your doubts. 

FavTutor - 24x7 Live Coding Help from Expert Tutors!

About The Author
Shivali Bhadaniya
I'm Shivali Bhadaniya, a computer engineer student and technical content writer, very enthusiastic to learn and explore new technologies and looking towards great opportunities. It is amazing for me to share my knowledge through my content to help curious minds.