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
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.
