Print all pairs of anagrams in a set of strings
Given a set of strings, print all pairs of anagrams together. Two strings, X and Y, are called anagrams if we can get a string Y by rearranging the letters of the string X and using all the characters of the string X exactly once.
For example, the following word pairs are anagrams since we can rearrange the first string to get the second string and vice-versa. The problem requires the anagrams to be grouped.
(altered, related)
(auctioned, education)
(aspired, despair)
(mastering, streaming)
In the previous post, we have discussed a solution using a hash table. In this post, we will cover the Trie-based solution. The idea is simple – construct an empty Trie and do the following for each word:
- Sort characters of the current word.
- Insert the sorted word into our Trie.
- Store the current unsorted word in the leaf node of the sorted word tree so that all anagrams will end up at the same leaf node.
Finally, traverse the Trie in a preorder fashion and print all anagrams together. The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
#include <iostream> #include <vector> #include <map> #include <string> #include <algorithm> using namespace std; // Data structure to store a Trie node struct TrieNode { // each node stores a map to its child nodes map<char, TrieNode*> child; // stores anagrams in the leaf node string words; }; // Function to insert a string into a Trie void insert(TrieNode* &root, string word, string originalWord) { // start from the root node TrieNode* curr = root; for (char c: word) { // create a new node if the path doesn't exist if (curr->child.find(c) == curr->child.end()) { curr->child[c] = new TrieNode(); } // go to the next node curr = curr->child[c]; } // anagrams will end up at the same leaf node curr->words += originalWord + ' '; } // A recursive function that traverses a Trie in preorder fashion and // prints all anagrams together void printAnagrams(TrieNode *root) { // base case if (root == nullptr) { return; } // print the current word if (root->words.length() > 1) { cout << root->words << endl; } // recur for all child nodes for (auto &child: root->child) { printAnagrams(child.second); } } // Function to group anagrams from a given list of words void groupAnagrams(vector<string> &words) { // construct an empty trie TrieNode* root = new TrieNode(); // do for each word for (string word: words) { // Sort the characters of the current word and insert it into the Trie. // The original word gets stored in the leaf node string sorted = word; sort(sorted.begin(), sorted.end()); insert(root, sorted, word); } // print all anagrams together printAnagrams(root); } int main() { vector<string> words = { "auctioned", "actors", "altered", "streaming", "related", "education", "aspired", "costar", "despair", "mastering" }; groupAnagrams(words); return 0; } |
Output:
auctioned education
actors costar
altered related
aspired despair
streaming mastering
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
import java.util.Arrays; import java.util.HashMap; import java.util.Map; import java.util.stream.Collectors; import java.util.stream.Stream; // A class to store a Trie node class TrieNode { // each node stores a map to its child nodes Map<Character, TrieNode> child = new HashMap<>(); // stores anagrams in the leaf node String words = ""; } class Main { // Function to insert a string into a Trie public static void insert(TrieNode root, String word, String originalWord) { // start from the root node TrieNode curr = root; for (char c: word.toCharArray()) { // create a new node if the path doesn't exist curr.child.putIfAbsent(c, new TrieNode()); // go to the next node curr = curr.child.get(c); } // anagrams will end up at the same leaf node curr.words += originalWord + " "; } // A recursive function that traverses a Trie in preorder fashion and // prints all anagrams together public static void printAnagrams(TrieNode root) { // base case if (root == null) { return; } // print the current word if (root.words.length() > 1) { System.out.println(root.words); } // recur for all child nodes for (TrieNode child: root.child.values()) { printAnagrams(child); } } // Function to group anagrams from a given list of words public static void groupAnagrams(String[] words) { // construct an empty trie TrieNode root = new TrieNode(); // do for each word for (String word: words) { // Sort the characters of the current word and insert it into the Trie. // The original word gets stored in the leaf node String sorted = Stream.of(word.toCharArray()) .map(chars -> { Arrays.sort(chars); return new String(chars); }) .collect(Collectors.joining()); insert(root, sorted, word); } // print all anagrams together printAnagrams(root); } public static void main(String[] args) { String[] words = { "auctioned", "actors", "altered", "streaming", "related", "education", "aspired", "costar", "despair", "mastering" }; groupAnagrams(words); } } |
Output:
auctioned education
actors costar
altered related
aspired despair
streaming mastering
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
# A class to store a Trie node class TrieNode: def __init__(self): # each node stores a dictionary to its child nodes self.child = {} # stores anagrams in the leaf node self.words = [] # Function to insert a string into a Trie def insert(root, word, originalWord): # start from the root node curr = root for c in word: # create a new node if the path doesn't exist curr.child.setdefault(c, TrieNode()) # go to the next node curr = curr.child[c] # anagrams will end up at the same leaf node curr.words.append(originalWord) # A recursive function that traverses a Trie in preorder fashion and # prints all anagrams together def printAnagrams(root): # base case if root is None: return # print the current word if len(root.words) > 1: print(root.words) # recur for all child nodes for child in root.child.values(): printAnagrams(child) # Function to group anagrams from a given list of words def groupAnagrams(words): # construct an empty trie root = TrieNode() # do for each word for word in words: # Sort the characters of the current word and insert it into the Trie. # Note that the original word gets stored on the leaf insert(root, ''.join(sorted(word)), word) # print all anagrams together printAnagrams(root) if __name__ == '__main__': words = [ 'auctioned', 'actors', 'altered', 'streaming', 'related', 'education', 'aspired', 'costar', 'despair', 'mastering' ] groupAnagrams(words) |
Output:
[‘auctioned’, ‘education’]
[‘actors’, ‘costar’]
[‘altered’, ‘related’]
[‘aspired’, ‘despair’]
[‘streaming’, ‘mastering’]
The time complexity of the above solution is O(N × M × log(M)), where N is the total number of words and M is the maximum word length.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)