Implementar un Directorio Telefónico

Dada una lista de contactos que existen en un directorio telefónico. La tarea es implementar la consulta de búsqueda para el directorio telefónico. La consulta de búsqueda en una string ‘ str ‘ muestra todos los contactos que tienen el prefijo ‘ str ‘. Una propiedad especial de la función de búsqueda es que, cuando un usuario busca un contacto de la lista de contactos, se muestran sugerencias (contactos con prefijo como la string ingresada) después de que el usuario ingresa cada carácter.

Nota: los contactos en la lista consisten solo en minúsculas.

Ejemplo:

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" 

El directorio telefónico se puede implementar de manera eficiente utilizando Trie Data Structure. Insertamos todos los contactos en Trie.

Generalmente, la consulta de búsqueda en un Trie es para determinar si la string está presente o no en el trie, pero en este caso se nos pide encontrar todas las strings con cada prefijo de ‘str’. Esto es equivalente a hacer un recorrido DFS en un gráfico . Desde un Node Trie, visite los Nodes Trie adyacentes y hágalo recursivamente hasta que no haya más adyacentes. Esta función recursiva tomará 2 argumentos, uno como Trie Node que apunta al Trie Node actual que se está visitando y otro como la string que almacena la string encontrada hasta el momento con el prefijo ‘str’.
Cada Trie Node almacena una variable booleana ‘isLast’ que es verdadera si el Node representa el final de un contacto (palabra).

// 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)

El usuario ingresará la string carácter por carácter y necesitamos mostrar sugerencias con el prefijo formado después de cada carácter ingresado.
Entonces, un enfoque para encontrar el prefijo que comienza con la string formada es verificar si el prefijo existe en el Trie, si es así, llame a la función displayContacts(). En este enfoque, después de cada carácter ingresado, verificamos si la string existe en el Trie.
En lugar de verificar una y otra vez, podemos mantener un puntero prevNode‘ que apunta al TrieNode que corresponde al último carácter ingresado por el usuario, ahora debemos verificar el Node secundario para el ‘prevNode’ cuando el usuario ingresa otro carácter para verificar si existe en el Trie. Si el nuevo prefijo no está en Trie, entonces toda la string que se forma ingresando caracteres después de ‘prefijo’ tampoco se puede encontrar en Trie. Entonces rompemos el bucle que se usa para generar prefijos uno por uno e imprimimos «No se encontraron resultados» para todos los caracteres restantes.

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("\nNo 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("\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

Producción:

Suggestions based on "g" are 
geeksquiz
gforgeeks

Suggestions based on "ge" are 
geeksquiz

No Results Found for "gek" 

No Results Found for "gekk" 

Este artículo es una contribución de Chirag Agarwal . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *