電話帳を実装する
GfG Practice で試してみる 
#practiceLinkDiv { 表示: なし !重要; }
出力
#practiceLinkDiv { 表示: なし !重要; } 電話帳に存在する連絡先のリストが与えられたとします。タスクは、電話帳の検索クエリを実装することです。文字列「'」に対する検索クエリ str ' は、接頭辞が ' であるすべての連絡先を表示します。 str 』。検索機能の特別なプロパティの 1 つは、ユーザーが連絡先リストから連絡先を検索するときに、ユーザーが各文字を入力した後に候補 (入力された文字列としてプレフィックスを持つ連絡先) が表示されることです。
注記： リスト内の連絡先は小文字のアルファベットのみで構成されています。 例：
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' 推奨: で解決してください 練習する 解決策に進む前に、まず。
電話帳は、次を使用して効率的に実装できます。 トライ データ構造。すべての連絡先を Trie に挿入します。一般に、トライに対する検索クエリは、トライ内に文字列が存在するかどうかを判断することですが、この場合は、各プレフィックスが「str」であるすべての文字列を検索するように求められます。これは、次のことを行うのと同じです。 グラフ上の DFS トラバーサル 。 Trie ノードから隣接する Trie ノードにアクセスし、隣接する Trie ノードがなくなるまでこれを再帰的に実行します。この再帰関数は 2 つの引数を受け取ります。1 つはアクセスされている現在のトライ ノードを指すトライ ノードとして、もう 1 つはこれまでに見つかった文字列を格納する文字列としてプレフィックス「str」を付けます。各トライ ノードはブール変数「isLast」を格納します。これは、ノードがコンタクト (単語) の終わりを表す場合に true になります。
// 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)
ユーザーは文字列を 1 文字ずつ入力します。入力されたすべての文字の後に形成されるプレフィックスを使用して候補を表示する必要があります。したがって、形成された文字列で始まるプレフィックスを見つける 1 つの方法は、プレフィックスが Trie if Yes に存在するかどうかを確認してから、displayContacts() 関数を呼び出すことです。このアプローチでは、文字を入力するたびに、その文字列がトライに存在するかどうかをチェックします。何度も確認する代わりに、ポインタを維持できます。 前のノード ' これは、ユーザーが最後に入力した文字に対応する TrieNode を指します。今度は、ユーザーが別の文字を入力したときに、子ノードの 'prevNode' をチェックして、その文字がトライ内に存在するかどうかを確認する必要があります。新しいプレフィックスが Trie にない場合、「prefix」の後に文字を入力して形成されるすべての文字列も Trie で見つかりません。そこで、プレフィックスを 1 つずつ生成するために使用されているループを中断し、残りのすべての文字に対して「結果が見つかりません」と出力します。
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>
出力
Suggestions based on gare geeksquiz gforgeeks Suggestions based on geare geeksquiz No Results Found for gek No Results Found for gekk
時間計算量: O(n*m) ここで、n はコンタクトの数、m はコンタクト文字列の最大長です。
補助スペース: O(n*m)
