给出电话簿中的联系人列表。任务是实现电话目录的搜索查询。对字符串的搜索查询 str ‘显示前缀为’ str ’. 搜索功能的一个特殊属性是，当用户从联系人列表中搜索联系人时，在用户输入每个字符后，会显示建议（前缀为输入的字符串的联系人）。
null
注：列表中的联系人仅由小写字母组成。
例子：
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。
通常，对Trie的搜索查询是为了确定Trie中是否存在该字符串，但在这种情况下，我们需要查找每个前缀为“str”的所有字符串。这相当于做一个 图上的DFS遍历 .从一个Trie节点，访问相邻的Trie节点，并递归执行此操作，直到不再有相邻节点。这个递归函数将使用两个参数，一个作为Trie节点，指向正在访问的当前Trie节点，另一个作为字符串，存储到目前为止找到的前缀为“str”的字符串。 每个Trie节点都存储一个布尔变量“isLast”，如果该节点表示联系人（word）的结束，则该变量为真。
// 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)
用户将一个字符一个字符地输入字符串，我们需要在每个输入的字符后显示前缀建议。 因此，查找以所形成字符串开头的前缀的一种方法是检查Trie中是否存在前缀，如果存在，则调用displayContacts（）函数。在这种方法中，在输入每个字符后，我们检查Trie中是否存在字符串。 我们可以维护一个指针，而不是一次又一次地检查 前淋巴结 ‘这指向与用户上次输入的字符相对应的三节点，现在我们需要在用户输入另一个字符时检查子节点的’prevNode’，以检查它是否存在于Trie中。如果新前缀不在Trie中，那么在“prefix”之后输入字符形成的所有字符串也无法在Trie中找到。因此，我们打破了用于逐个生成前缀的循环，并为所有剩余字符打印“未找到结果”。
C++
// C++ Program to Implement a Phone // Directory Using Trie Data Structure #include <bits/stdc++.h> 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 << "nNo Results Found for " " << prefix << "" n"; i++; break ; } // If present in trie then display all // the contacts with given prefix. cout << "nSuggestions based on " " << prefix << "" are n"; 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 << "nNo 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); } } |
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( "No Results Found for'" + prefix + "'" ); i++; break ; } // If present in trie then display all // the contacts with given prefix. Console.WriteLine( "Suggestions based on '" + prefix + "' are" ); displayContactsUtil(curNode, prefix); // Change prevNode for next prefix prevNode = curNode; } for ( ; i < len; i++) { prefix += str[i]; Console.WriteLine( "No 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 |
输出：
Suggestions based on "g" are geeksquiz gforgeeks Suggestions based on "ge" are geeksquiz No Results Found for "gek" No Results Found for "gekk"
本文由 希拉格·阿加瓦尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 贡献极客。组织 或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
