Print Strings In Reverse Dictionary Order Using Trie
Trie is an efficient information retrieval data structure. Using Trie, search complexities can be brought to an optimal limit.
Given an array of strings. The task is to print all strings in reverse dictionary order using Trie. If there are duplicates in the input array, we need to print them only once.
Examples:
Input: str = {"cat", "there", "caller", "their", "calling"} Output: there their cat calling caller root / \ c t | | a h | \ | l t e | | \ l i r | \ | | e i r e | | r n | g Input: str = {"Candy", "cat", "Caller", "calling"} Output: cat candy calling caller root | c | a / | \ l n t | | l d | \ | e i y | | r n | g
Approach:
To solve the problem mentioned above, first, construct a Trie using all strings then print a string of rightmost subtree from top to bottom then print a string of second right subtree from top to bottom then print for third right subtree and so on. It is similar to preorder traversal of a tree from right to left.
Below is the implementation of the above approach:
C++
// C++ program to print array of string // in reverse dictionary order using trie #include <bits/stdc++.h> using namespace std; #define CHILDREN 26 #define MAX 100 // Trie node struct trie { trie* child[CHILDREN]; // endOfWord is true // if the node represents // end of a word bool endOfWord; }; // Function will return // the new node initialized NULL trie* createNode() { trie* temp = new trie(); temp->endOfWord = false ; for ( int i = 0; i < CHILDREN; i++) { // Initialize null to the all child temp->child[i] = NULL; } return temp; } // Function will insert the // string in a trie recursively void insertRecursively(trie* itr, string str, int i) { if (i < str.length()) { int index = str[i] - 'a' ; if (itr->child[index] == NULL) { // Create a new node itr->child[index] = createNode(); } // Recursive call for insertion of string insertRecursively(itr->child[index], str, i + 1); } else { // Make the endOfWord // true which represents // the end of string itr->endOfWord = true ; } } // Function call to insert a string void insert(trie* itr, string str) { // Function call with necessary arguments insertRecursively(itr, str, 0); } // Function to check whether the node is leaf or not bool isLeafNode(trie* root) { return root->endOfWord != false ; } // Function to display the content of trie void displayContent(trie* root, char str[], int level) { // If node is leaf node, it indicates end // of string, so a null character is added // and string is displayed if (isLeafNode(root)) { // Assign a null character in temporary string str[level] = '\0' ; cout << str << endl; } for ( int i = CHILDREN - 1; i >= 0; i--) { // check if NON NULL child is found // add parent key to str and // call the display function recursively // for child node if (root->child[i]) { str[level] = i + 'a' ; displayContent(root->child[i], str, level + 1); } } } // Function call for displaying content void display(trie* itr) { int level = 0; char str[MAX]; displayContent(itr, str, level); } // Driver code int main() { trie* root = createNode(); insert(root, "their" ); insert(root, "there" ); insert(root, "answer" ); insert(root, "any" ); /* After inserting strings, trie will look like root / \ a t | | n h | \ | s y e | | \ w i r | | | e r e | r */ display(root); return 0; } |
Java
// Java program to print array of string // in reverse dictionary order using trie import java.util.Scanner; public class Main { private static final int CHILDREN = 26 ; private static final int MAX = 100 ; // Trie node private static class Trie { Trie[] child = new Trie[CHILDREN]; // endOfWord is true // if the node represents // end of a word boolean endOfWord; Trie() { endOfWord = false ; for ( int i = 0 ; i < CHILDREN; i++) { child[i] = null ; } } } // Function will return // the new node initialized NULL private static Trie createNode() { return new Trie(); } // Function will insert the // string in a trie recursively private static void insertRecursively(Trie itr, String str, int i) { if (i < str.length()) { int index = str.charAt(i) - 'a' ; if (itr.child[index] == null ) { // Create a new node itr.child[index] = createNode(); } // Recursive call for insertion of string insertRecursively(itr.child[index], str, i + 1 ); } else { // Make the endOfWord // true which represents // the end of string itr.endOfWord = true ; } } // Function call to insert a string private static void insert(Trie itr, String str) { // Function call with necessary arguments insertRecursively(itr, str, 0 ); } // Function to check whether the node is leaf or not private static boolean isLeafNode(Trie root) { return root.endOfWord; } // Function to display the content of trie private static void displayContent(Trie root, char [] str, int level) { // If node is leaf node, it indicates end // of string, so a null character is added // and string is displayed if (isLeafNode(root)) { // Assign a null character in temporary string str[level] = '\0' ; System.out.println(str); } for ( int i = CHILDREN - 1 ; i >= 0 ; i--) { // check if NON NULL child is found // add parent key to str and // call the display function recursively // for child node if (root.child[i] != null ) { str[level] = ( char )(i + 'a' ); displayContent(root.child[i], str, level + 1 ); } } } // Function call for displaying content private static void display(Trie itr) { int level = 0 ; char [] str = new char [MAX]; displayContent(itr, str, level); } // Driver code public static void main(String[] args) { Trie root = createNode(); insert(root, "their" ); insert(root, "there" ); insert(root, "answer" ); insert(root, "any" ); /* After inserting strings, trie will look like root / \ a t | | n h | \ | s y e | | \ w i r | | | e r e | r */ display(root); } } // This code is contributed by Aman Kumar |
Python3
# Python3 program to print array of string # in reverse dictionary order using trie CHILDREN = 26 MAX = 100 # Trie node class trie: def __init__( self ): self .child = [ 0 for i in range (CHILDREN)] # endOfWord is true # if the node represents # end of a word self .endOfWord = False ; # Function will return # the new node initialized NONE def createNode(): temp = trie(); temp.endOfWord = False ; for i in range (CHILDREN): # Initialize null to the all child temp.child[i] = None ; return temp; # Function will insert the # string in a trie recursively def insertRecursively(itr, str , i): if (i < len ( str )): index = ord ( str [i]) - ord ( 'a' ); if (itr.child[index] = = None ): # Create a new node itr.child[index] = createNode(); # Recursive call for insertion of string insertRecursively(itr.child[index], str , i + 1 ); else : # Make the endOfWord # true which represents # the end of string itr.endOfWord = True ; # Function call to insert a string def insert(itr, str ): # Function call with necessary arguments insertRecursively(itr, str , 0 ); # Function to check whether the node is leaf or not def isLeafNode(root): return root.endOfWord ! = False ; # Function to display the content of trie def displayContent(root, str , level): # If node is leaf node, it indicates end # of string, so a null character is added # and string is displayed if (isLeafNode(root)): # Assign a null character in temporary string print ("".join( str [:level])) for i in range (CHILDREN - 1 , - 1 , - 1 ): # check if NON NONE child is found # add parent key to str and # call the display function recursively # for child node if (root.child[i]): str [level] = chr (i + ord ( 'a' )); displayContent(root.child[i], str , level + 1 ); # Function call for displaying content def display(itr): level = 0 ; str = ['' for i in range ( MAX )]; displayContent(itr, str , level); # Driver code if __name__ = = '__main__' : root = createNode(); insert(root, "their" ); insert(root, "there" ); insert(root, "answer" ); insert(root, "any" ); ''' After inserting strings, trie will look like root / \ a t | | n h | \ | s y e | | \ w i r | | | e r e | r ''' display(root); # This code is contributed by rutvik_56 |
C#
// C# program to print array of string // in reverse dictionary order using trie using System; public class GFG { private const int CHILDREN = 26; private const int MAX = 100; // Trie node private class Trie { public Trie[] Child = new Trie[CHILDREN]; // endOfWord is true // if the node represents // end of a word public bool EndOfWord; public Trie() { EndOfWord = false ; for ( int i = 0; i < CHILDREN; i++) { Child[i] = null ; } } } // Function will return // the new node initialized NULL private static Trie CreateNode() { return new Trie(); } // Function will insert the // string in a trie recursively private static void InsertRecursively(Trie itr, string str, int i) { if (i < str.Length) { int index = str[i] - 'a' ; if (itr.Child[index] == null ) { // Create a new node itr.Child[index] = CreateNode(); } // Recursive call for insertion of string InsertRecursively(itr.Child[index], str, i + 1); } else { // Make the endOfWord // true which represents // the end of string itr.EndOfWord = true ; } } // Function call to insert a string private static void Insert(Trie itr, string str) { // Function call with necessary arguments InsertRecursively(itr, str, 0); } // Function to check whether the node is leaf or not private static bool IsLeafNode(Trie root) { return root.EndOfWord; } // Function to display the content of trie private static void DisplayContent(Trie root, char [] str, int level) { // If node is leaf node, it indicates end // of string, so a null character is added // and string is displayed if (IsLeafNode(root)) { // Assign a null character in temporary string str[level] = '\0' ; Console.WriteLine( new string (str)); } for ( int i = CHILDREN - 1; i >= 0; i--) { // check if NON NULL child is found // add parent key to str and // call the display function recursively // for child node if (root.Child[i] != null ) { str[level] = ( char )(i + 'a' ); DisplayContent(root.Child[i], str, level + 1); } } } // Function call for displaying content private static void Display(Trie itr) { int level = 0; char [] str = new char [MAX]; DisplayContent(itr, str, level); } // Driver code public static void Main( string [] args) { Trie root = CreateNode(); Insert(root, "their" ); Insert(root, "there" ); Insert(root, "answer" ); Insert(root, "any" ); /* After inserting strings, trie will look like root / \ a t | | n h | \ | s y e | | \ w i r | | | e r e | r */ Display(root); } } |
Javascript
// Javascript program to print array of string // in reverse dictionary order using trie const CHILDREN = 26; const MAX = 100; // Trie node class TrieNode { constructor() { this .child = new Array(CHILDREN); this .endOfWord = false ; } } // Function will return the new node initialized NULL function createNode() { const temp = new TrieNode(); for (let i = 0; i < CHILDREN; i++) { // Initialize null to the all child temp.child[i] = null ; } return temp; } // Function will insert the string in a trie recursively function insertRecursively(itr, str, i) { if (i < str.length) { const index = str.charCodeAt(i) - 97; if (itr.child[index] == null ) { // Create a new node itr.child[index] = createNode(); } // Recursive call for insertion of string insertRecursively(itr.child[index], str, i + 1); } else { // Make the endOfWord true which represents the end of string itr.endOfWord = true ; } } // Function call to insert a string function insert(itr, str) { // Function call with necessary arguments insertRecursively(itr, str, 0); } // Function to check whether the node is leaf or not function isLeafNode(root) { return root.endOfWord !== false ; } // Function to display the content of trie function displayContent(root, str, level) { // If node is leaf node, it indicates end // of string, so a null character is added // and string is displayed if (isLeafNode(root)) { // Assign a null character in temporary string str[level] = '\0' ; console.log(str.join( '' )+ "<br>" ); } for (let i = CHILDREN - 1; i >= 0; i--) { // check if NON NULL child is found // add parent key to str and // call the display function recursively // for child node if (root.child[i]) { str[level] = String.fromCharCode(i + 97); displayContent(root.child[i], str, level + 1); } } } // Function call for displaying content function display(itr) { const level = 0; const str = new Array(MAX); displayContent(itr, str, level); } // Driver code const root = createNode(); insert(root, "their" ); insert(root, "there" ); insert(root, "answer" ); insert(root, "any" ); /* After inserting strings, trie will look like root / \ a t | | n h | \ | s y e | | \ w i r | | | e r e | r */ display(root); // This code is contributed by Pushpesh Raj. |
there their any answer
Time Complexity: O(N*M*log(M)) where N is the total number of nodes in the trie, and M is the length of the longest string in the trie.
Auxiliary Space: O(N*M)