Implementirajte telefonski imenik
Isprobajte na GfG Practice 
#practiceLinkDiv { display: none !important; }
Izlaz
#practiceLinkDiv { display: none !important; } Dat je popis kontakata koji postoje u telefonskom imeniku. Zadatak je implementirati upit za pretraživanje telefonskog imenika. Upit za pretraživanje niza ' str ' prikazuje sve kontakte koji imaju prefiks ' str ’. Jedno posebno svojstvo funkcije pretraživanja je da kada korisnik traži kontakt s popisa kontakata, tada se prijedlozi (Kontakti s prefiksom kao unesenim nizom) prikazuju nakon što korisnik unese svaki znak.
Bilješka: Kontakti na popisu sastoje se samo od malih slova. Primjer:
Input : contacts [] = {gforgeeks geeksquiz } Query String = gekk Output : Suggestions based on 'g' are geeksquiz gforgeeks Suggestions based on 'ge' are geeksquiz No Results Found for 'gek' No Results Found for 'gekk' Preporučeno: riješite ga na PRAKSA prvo prije nego prijeđete na rješenje.
Telefonski imenik može se učinkovito implementirati korištenjem Pokušaj Struktura podataka. Sve kontakte ubacujemo u Trie. Općenito, upit za pretraživanje na trie je da se utvrdi je li niz prisutan ili ne u trie, ali u ovom slučaju od nas se traži da pronađemo sve nizove sa svakim prefiksom 'str'. Ovo je jednako kao da radite a DFS obilazak na grafu . Iz Trie čvora posjetite susjedne Trie čvorove i radite to rekurzivno sve dok više ne bude susjednih. Ova rekurzivna funkcija će uzeti 2 argumenta jedan kao Trie čvor koji pokazuje na trenutni posjećeni Trie čvor i drugi kao niz koji pohranjuje do sada pronađeni niz s prefiksom kao 'str'. Svaki Trie čvor pohranjuje booleovu varijablu 'isLast' koja je istinita ako čvor predstavlja kraj kontakta (riječi).
// This function displays all words with given // prefix. 'node' represents last node when // path from root follows characters of 'prefix'. displayContacts (TreiNode node string prefix) If (node.isLast is true) display prefix // finding adjacent nodes for each character ‘i’ in lower case Alphabets if (node.child[i] != NULL) displayContacts(node.child[i] prefix+i)
Korisnik će niz unositi znak po znak, a mi trebamo prikazati prijedloge s prefiksom formiranim nakon svakog unesenog znaka. Dakle, jedan pristup pronalaženju prefiksa koji počinje formiranim nizom je provjera postoji li prefiks u Trie, ako da, zatim pozivanje funkcije displayContacts(). U ovom pristupu nakon svakog unesenog znaka provjeravamo da li string postoji u Trie. Umjesto stalnog provjeravanja možemo zadržati pokazivač prevNode ' koji pokazuje na TrieNode koji odgovara zadnjem unesenom znaku od strane korisnika, a sada moramo provjeriti podređeni čvor za 'prevNode' kada korisnik unese drugi znak kako bismo provjerili postoji li u Trie. Ako novi prefiks nije u Trie-u, tada se svi nizovi koji su formirani unosom znakova nakon 'prefiksa' ne mogu pronaći ni u Trie-u. Tako prekidamo petlju koja se koristi za generiranje prefiksa jedan po jedan i ispisujemo 'No Result Found' za sve preostale znakove.
C++ // C++ Program to Implement a Phone // Directory Using Trie Data Structure #include using namespace std ; struct TrieNode { // Each Trie Node contains a Map 'child' // where each alphabet points to a Trie // Node. // We can also use a fixed size array of // size 256. unordered_map < char TrieNode *> child ; // 'isLast' is true if the node represents // end of a contact bool isLast ; // Default Constructor TrieNode () { // Initialize all the Trie nodes with NULL for ( char i = 'a' ; i <= 'z' ; i ++ ) child [ i ] = NULL ; isLast = false ; } }; // Making root NULL for ease so that it doesn't // have to be passed to all functions. TrieNode * root = NULL ; // Insert a Contact into the Trie void insert ( string s ) { int len = s . length (); // 'itr' is used to iterate the Trie Nodes TrieNode * itr = root ; for ( int i = 0 ; i < len ; i ++ ) { // Check if the s[i] is already present in // Trie TrieNode * nextNode = itr -> child [ s [ i ]]; if ( nextNode == NULL ) { // If not found then create a new TrieNode nextNode = new TrieNode (); // Insert into the Map itr -> child [ s [ i ]] = nextNode ; } // Move the iterator('itr') to point to next // Trie Node itr = nextNode ; // If its the last character of the string 's' // then mark 'isLast' as true if ( i == len - 1 ) itr -> isLast = true ; } } // This function simply displays all dictionary words // going through current node. String 'prefix' // represents string corresponding to the path from // root to curNode. void displayContactsUtil ( TrieNode * curNode string prefix ) { // Check if the string 'prefix' ends at this Node // If yes then display the string found so far if ( curNode -> isLast ) cout < < prefix < < endl ; // Find all the adjacent Nodes to the current // Node and then call the function recursively // This is similar to performing DFS on a graph for ( char i = 'a' ; i <= 'z' ; i ++ ) { TrieNode * nextNode = curNode -> child [ i ]; if ( nextNode != NULL ) displayContactsUtil ( nextNode prefix + ( char ) i ); } } // Display suggestions after every character enter by // the user for a given query string 'str' void displayContacts ( string str ) { TrieNode * prevNode = root ; string prefix = '' ; int len = str . length (); // Display the contact List for string formed // after entering every character int i ; for ( i = 0 ; i < len ; i ++ ) { // 'prefix' stores the string formed so far prefix += ( char ) str [ i ]; // Get the last character entered char lastChar = prefix [ i ]; // Find the Node corresponding to the last // character of 'prefix' which is pointed by // prevNode of the Trie TrieNode * curNode = prevNode -> child [ lastChar ]; // If nothing found then break the loop as // no more prefixes are going to be present. if ( curNode == NULL ) { cout < < ' n No Results Found for ' < < prefix < < ' n ' ; i ++ ; break ; } // If present in trie then display all // the contacts with given prefix. cout < < ' n Suggestions based on ' < < prefix < < 'are ' ; displayContactsUtil ( curNode prefix ); // Change prevNode for next prefix prevNode = curNode ; } // Once search fails for a prefix we print // 'Not Results Found' for all remaining // characters of current query string 'str'. for (; i < len ; i ++ ) { prefix += ( char ) str [ i ]; cout < < ' n No Results Found for ' < < prefix < < ' n ' ; } } // Insert all the Contacts into the Trie void insertIntoTrie ( string contacts [] int n ) { // Initialize root Node root = new TrieNode (); // Insert each contact into the trie for ( int i = 0 ; i < n ; i ++ ) insert ( contacts [ i ]); } // Driver program to test above functions int main () { // Contact list of the User string contacts [] = { 'gforgeeks' 'geeksquiz' }; // Size of the Contact List int n = sizeof ( contacts ) / sizeof ( string ); // Insert all the Contacts into Trie insertIntoTrie ( contacts n ); string query = 'gekk' ; // Note that the user will enter 'g' then 'e' so // first display all the strings with prefix as 'g' // and then all the strings with prefix as 'ge' displayContacts ( query ); return 0 ; }
Java // Java Program to Implement a Phone // Directory Using Trie Data Structure import java.util.* ; class TrieNode { // Each Trie Node contains a Map 'child' // where each alphabet points to a Trie // Node. HashMap < Character TrieNode > child ; // 'isLast' is true if the node represents // end of a contact boolean isLast ; // Default Constructor public TrieNode () { child = new HashMap < Character TrieNode > (); // Initialize all the Trie nodes with NULL for ( char i = 'a' ; i <= 'z' ; i ++ ) child . put ( i null ); isLast = false ; } } class Trie { TrieNode root ; // Insert all the Contacts into the Trie public void insertIntoTrie ( String contacts [] ) { root = new TrieNode (); int n = contacts . length ; for ( int i = 0 ; i < n ; i ++ ) { insert ( contacts [ i ] ); } } // Insert a Contact into the Trie public void insert ( String s ) { int len = s . length (); // 'itr' is used to iterate the Trie Nodes TrieNode itr = root ; for ( int i = 0 ; i < len ; i ++ ) { // Check if the s[i] is already present in // Trie TrieNode nextNode = itr . child . get ( s . charAt ( i )); if ( nextNode == null ) { // If not found then create a new TrieNode nextNode = new TrieNode (); // Insert into the HashMap itr . child . put ( s . charAt ( i ) nextNode ); } // Move the iterator('itr') to point to next // Trie Node itr = nextNode ; // If its the last character of the string 's' // then mark 'isLast' as true if ( i == len - 1 ) itr . isLast = true ; } } // This function simply displays all dictionary words // going through current node. String 'prefix' // represents string corresponding to the path from // root to curNode. public void displayContactsUtil ( TrieNode curNode String prefix ) { // Check if the string 'prefix' ends at this Node // If yes then display the string found so far if ( curNode . isLast ) System . out . println ( prefix ); // Find all the adjacent Nodes to the current // Node and then call the function recursively // This is similar to performing DFS on a graph for ( char i = 'a' ; i <= 'z' ; i ++ ) { TrieNode nextNode = curNode . child . get ( i ); if ( nextNode != null ) { displayContactsUtil ( nextNode prefix + i ); } } } // Display suggestions after every character enter by // the user for a given string 'str' void displayContacts ( String str ) { TrieNode prevNode = root ; // 'flag' denotes whether the string entered // so far is present in the Contact List String prefix = '' ; int len = str . length (); // Display the contact List for string formed // after entering every character int i ; for ( i = 0 ; i < len ; i ++ ) { // 'str' stores the string entered so far prefix += str . charAt ( i ); // Get the last character entered char lastChar = prefix . charAt ( i ); // Find the Node corresponding to the last // character of 'str' which is pointed by // prevNode of the Trie TrieNode curNode = prevNode . child . get ( lastChar ); // If nothing found then break the loop as // no more prefixes are going to be present. if ( curNode == null ) { System . out . println ( 'nNo Results Found for ' + prefix ); i ++ ; break ; } // If present in trie then display all // the contacts with given prefix. System . out . println ( 'nSuggestions based on ' + prefix + ' are ' ); displayContactsUtil ( curNode prefix ); // Change prevNode for next prefix prevNode = curNode ; } for ( ; i < len ; i ++ ) { prefix += str . charAt ( i ); System . out . println ( 'nNo Results Found for ' + prefix ); } } } // Driver code class Main { public static void main ( String args [] ) { Trie trie = new Trie (); String contacts [] = { 'gforgeeks' 'geeksquiz' }; trie . insertIntoTrie ( contacts ); String query = 'gekk' ; // Note that the user will enter 'g' then 'e' so // first display all the strings with prefix as 'g' // and then all the strings with prefix as 'ge' trie . displayContacts ( query ); } }
Python3 # Python Program to Implement a Phone # Directory Using Trie Data Structure class TrieNode : def __init__ ( self ): # Each Trie Node contains a Map 'child' # where each alphabet points to a Trie # Node. self . child = {} self . is_last = False # Making root NULL for ease so that it doesn't # have to be passed to all functions. root = TrieNode () # Insert a Contact into the Trie def insert ( string ): # 'itr' is used to iterate the Trie Nodes itr = root for char in string : # Check if the s[i] is already present in # Trie if char not in itr . child : # If not found then create a new TrieNode itr . child [ char ] = TrieNode () # Move the iterator('itr') to point to next # Trie Node itr = itr . child [ char ] # If its the last character of the string 's' # then mark 'isLast' as true itr . is_last = True # This function simply displays all dictionary words # going through current node. String 'prefix' # represents string corresponding to the path from # root to curNode. def display_contacts_util ( cur_node prefix ): # Check if the string 'prefix' ends at this Node # If yes then display the string found so far if cur_node . is_last : print ( prefix ) # Find all the adjacent Nodes to the current # Node and then call the function recursively # This is similar to performing DFS on a graph for i in range ( ord ( 'a' ) ord ( 'z' ) + 1 ): char = chr ( i ) next_node = cur_node . child . get ( char ) if next_node : display_contacts_util ( next_node prefix + char ) # Display suggestions after every character enter by # the user for a given query string 'str' def displayContacts ( string ): prev_node = root prefix = '' # Display the contact List for string formed # after entering every character for i char in enumerate ( string ): # 'prefix' stores the string formed so far prefix += char # Find the Node corresponding to the last # character of 'prefix' which is pointed by # prevNode of the Trie cur_node = prev_node . child . get ( char ) # If nothing found then break the loop as # no more prefixes are going to be present. if not cur_node : print ( f 'No Results Found for { prefix } n ' ) break # If present in trie then display all # the contacts with given prefix. print ( f 'Suggestions based on { prefix } are ' end = ' ' ) display_contacts_util ( cur_node prefix ) print () # Change prevNode for next prefix prev_node = cur_node # Once search fails for a prefix we print # 'Not Results Found' for all remaining # characters of current query string 'str'. for char in string [ i + 1 :]: prefix += char print ( f 'No Results Found for { prefix } n ' ) # Insert all the Contacts into the Trie def insertIntoTrie ( contacts ): # Insert each contact into the trie for contact in contacts : insert ( contact ) # Driver program to test above functions # Contact list of the User contacts = [ 'gforgeeks' 'geeksquiz' ] # Size of the Contact List n = len ( contacts ) # Insert all the Contacts into Trie insertIntoTrie ( contacts ) query = 'gekk' # Note that the user will enter 'g' then 'e' so # first display all the strings with prefix as 'g' # and then all the strings with prefix as 'ge' displayContacts ( query ) # This code is contributed by Aman Kumar
C# // C# Program to Implement a Phone // Directory Using Trie Data Structure using System ; using System.Collections.Generic ; class TrieNode { // Each Trie Node contains a Map 'child' // where each alphabet points to a Trie // Node. public Dictionary < char TrieNode > child ; // 'isLast' is true if the node represents // end of a contact public bool isLast ; // Default Constructor public TrieNode () { child = new Dictionary < char TrieNode > (); // Initialize all the Trie nodes with NULL for ( char i = 'a' ; i <= 'z' ; i ++ ) child . Add ( i null ); isLast = false ; } } class Trie { public TrieNode root ; // Insert all the Contacts into the Trie public void insertIntoTrie ( String [] contacts ) { root = new TrieNode (); int n = contacts . Length ; for ( int i = 0 ; i < n ; i ++ ) { insert ( contacts [ i ]); } } // Insert a Contact into the Trie public void insert ( String s ) { int len = s . Length ; // 'itr' is used to iterate the Trie Nodes TrieNode itr = root ; for ( int i = 0 ; i < len ; i ++ ) { // Check if the s[i] is already present in // Trie TrieNode nextNode = itr . child [ s [ i ]]; if ( nextNode == null ) { // If not found then create a new TrieNode nextNode = new TrieNode (); // Insert into the Dictionary if ( itr . child . ContainsKey ( s [ i ])) itr . child [ s [ i ]] = nextNode ; else itr . child . Add ( s [ i ] nextNode ); } // Move the iterator('itr') to point to next // Trie Node itr = nextNode ; // If its the last character of the string 's' // then mark 'isLast' as true if ( i == len - 1 ) itr . isLast = true ; } } // This function simply displays all dictionary words // going through current node. String 'prefix' // represents string corresponding to the path from // root to curNode. public void displayContactsUtil ( TrieNode curNode String prefix ) { // Check if the string 'prefix' ends at this Node // If yes then display the string found so far if ( curNode . isLast ) Console . WriteLine ( prefix ); // Find all the adjacent Nodes to the current // Node and then call the function recursively // This is similar to performing DFS on a graph for ( char i = 'a' ; i <= 'z' ; i ++ ) { TrieNode nextNode = curNode . child [ i ]; if ( nextNode != null ) { displayContactsUtil ( nextNode prefix + i ); } } } // Display suggestions after every character enter by // the user for a given string 'str' public void displayContacts ( String str ) { TrieNode prevNode = root ; // 'flag' denotes whether the string entered // so far is present in the Contact List String prefix = '' ; int len = str . Length ; // Display the contact List for string formed // after entering every character int i ; for ( i = 0 ; i < len ; i ++ ) { // 'str' stores the string entered so far prefix += str [ i ]; // Get the last character entered char lastChar = prefix [ i ]; // Find the Node corresponding to the last // character of 'str' which is pointed by // prevNode of the Trie TrieNode curNode = prevNode . child [ lastChar ]; // If nothing found then break the loop as // no more prefixes are going to be present. if ( curNode == null ) { Console . WriteLine ( 'nNo Results Found for ' + prefix ); i ++ ; break ; } // If present in trie then display all // the contacts with given prefix. Console . WriteLine ( 'nSuggestions based on ' + prefix + ' are ' ); displayContactsUtil ( curNode prefix ); // Change prevNode for next prefix prevNode = curNode ; } for ( ; i < len ; i ++ ) { prefix += str [ i ]; Console . WriteLine ( 'nNo Results Found for ' + prefix ); } } } // Driver code public class GFG { public static void Main ( String [] args ) { Trie trie = new Trie (); String [] contacts = { 'gforgeeks' 'geeksquiz' }; trie . insertIntoTrie ( contacts ); String query = 'gekk' ; // Note that the user will enter 'g' then 'e' so // first display all the strings with prefix as 'g' // and then all the strings with prefix as 'ge' trie . displayContacts ( query ); } } // This code is contributed by PrinciRaj1992
JavaScript < script > // Javascript Program to Implement a Phone // Directory Using Trie Data Structure class TrieNode { constructor () { // Each Trie Node contains a Map 'child' // where each alphabet points to a Trie // Node. // We can also use a fixed size array of // size 256. this . child = {}; // 'isLast' is true if the node represents // end of a contact this . isLast = false ; } } // Making root NULL for ease so that it doesn't // have to be passed to all functions. let root = null ; // Insert a Contact into the Trie function insert ( s ) { const len = s . length ; // 'itr' is used to iterate the Trie Nodes let itr = root ; for ( let i = 0 ; i < len ; i ++ ) { // Check if the s[i] is already present in // Trie const char = s [ i ]; let nextNode = itr . child [ char ]; if ( nextNode === undefined ) { // If not found then create a new TrieNode nextNode = new TrieNode (); // Insert into the Map itr . child [ char ] = nextNode ; } // Move the iterator('itr') to point to next // Trie Node itr = nextNode ; // If its the last character of the string 's' // then mark 'isLast' as true if ( i === len - 1 ) { itr . isLast = true ; } } } // This function simply displays all dictionary words // going through current node. String 'prefix' // represents string corresponding to the path from // root to curNode. function displayContactsUtil ( curNode prefix ) { // Check if the string 'prefix' ends at this Node // If yes then display the string found so far if ( curNode . isLast ) { document . write ( prefix + '
' ); } // Find all the adjacent Nodes to the current // Node and then call the function recursively // This is similar to performing DFS on a graph for ( let i = 97 ; i <= 122 ; i ++ ) { const char = String . fromCharCode ( i ); const nextNode = curNode . child [ char ]; if ( nextNode !== undefined ) { displayContactsUtil ( nextNode prefix + char ); } } } // Display suggestions after every character enter by // the user for a given query string 'str' function displayContacts ( str ) { let prevNode = root ; let prefix = '' ; const len = str . length ; // Display the contact List for string formed // after entering every character let i ; for ( i = 0 ; i < len ; i ++ ) { // 'prefix' stores the string formed so far prefix += str [ i ]; // Get the last character entered const lastChar = prefix [ i ]; // Find the Node corresponding to the last // character of 'prefix' which is pointed by // prevNode of the Trie const curNode = prevNode . child [ lastChar ]; // If nothing found then break the loop as // no more prefixes are going to be present. if ( curNode === undefined ) { document . write ( `No Results Found for ${ prefix } ` + '
' ); i ++ ; break ; } // If present in trie then display all // the contacts with given prefix. document . write ( `Suggestions based on ${ prefix } are ` ); displayContactsUtil ( curNode prefix ); document . write ( '
' ); // Change prevNode for next prefix prevNode = curNode ; } document . write ( '
' ); // Once search fails for a prefix we print // 'Not Results Found' for all remaining // characters of current query string 'str'. for (; i < len ; i ++ ) { prefix += str [ i ]; document . write ( 'No Results Found for ' + prefix + '
' ); } } // Insert all the Contacts into the Trie function insertIntoTrie ( contacts ) { // Initialize root Node root = new TrieNode (); const n = contacts . length ; // Insert each contact into the trie for ( let i = 0 ; i < n ; i ++ ) { insert ( contacts [ i ]); } } // Driver program to test above functions // Contact list of the User const contacts = [ 'gforgeeks' 'geeksquiz' ]; //Insert all the Contacts into Trie insertIntoTrie ( contacts ); const query = 'gekk' ; // Note that the user will enter 'g' then 'e' so // first display all the strings with prefix as 'g' // and then all the strings with prefix as 'ge' displayContacts ( query ); // This code is contributed by Utkarsh Kumar. < /script>
Izlaz
Suggestions based on gare geeksquiz gforgeeks Suggestions based on geare geeksquiz No Results Found for gek No Results Found for gekk
Vremenska složenost: O(n*m) gdje je n broj kontakata, a m najveća duljina niza kontakata.
Pomoćni prostor: O(n*m)
