实现一个电话目录

给出电话簿中的联系人列表。任务是实现电话目录的搜索查询。对字符串的搜索查询 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
喜欢就支持一下吧
点赞13 分享