Group anagrams are 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, you must understand the Group Anagrams Problem with solutions in Java, Python, and C++.
What is Group Anagrams Problem?
In the Group Anagrams Problem, you are given an array of strings and you have to group all the anagrams together. An anagram is a word or phrase formed by rearranging the letters of another word or phrase.
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 exist as an individual group and you can return that group in any order. Note that the order of the groups does not matter, but the order of strings within each group should be maintained.
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
Python Code for Group Anagrams
Here is the Python code to solve the Group Anagrams problem:
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
Here is the Java solution for this problem:
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
Below is the code in C++ to solve find and Group the 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; } }
How to Group Anagrams in a List in Python?
An anagram is a literary device, where the word, phrase, or name is rearranged to make a new word. An example could be, the letters of “William Shakespeare” can be rearranged to make the phrase “I'll make a wise phrase”, or the classic “Tom Marvolo Riddle” is rearranged to make “I am Lord Voldemort”.
To group anagrams in Python, we can use a dictionary in which the keys are lists of the definitions of each word and the values are lists of words listed in the same order. Basically, we use groups of words and their anagrams.
The ‘sorted()’ function is one such function to return the sorted characters of a word in alphabetical order. The resulting letters can then be combined to obtain an ordered version of the word.
Using this Python function, we can iterate over each word in the list to create its sorted version. If the sorted version already exists as a key in the dictionary, we can add the root word to the corresponding value, thus creating a dictionary with a key-value pair of the anagram.
Finally, the dictionary values are converted to a list and returned to the user. Each sub-list in this list contains words that are anagrams of each other.
words = ["eat", "tea", "tan", "ate", "nat", "bat"] anagram_groups = {} for word in words: sorted_word = ''.join(sorted(word)) if sorted_word in anagram_groups: anagram_groups[sorted_word].append(word) else: anagram_groups[sorted_word] = [word] result = list(anagram_groups.values()) print(result)
Output:
[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
Time Complexity
The running time complexity of the Group Anagrams 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.
Conclusion
TGroup 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 solving group anagram problems and their coding solution in Python, Java, and C++.
If you still find any difficult to solve the problem, please get in touch with our Live coding tutors with your doubts.
