Рубрики

Реализовать телефонный справочник

Приведен список контактов, которые существуют в телефонном справочнике. Задача — реализовать поисковый запрос для телефонного справочника. Поисковый запрос в строке ' str ' отображает все контакты с префиксом ' str '. Одно специальное свойство функции поиска состоит в том, что, когда пользователь ищет контакт из списка контактов, предложения (контакты с префиксом в качестве введенной строки) отображаются после того, как пользователь вводит каждый символ.

Примечание. Контакты в списке состоят только из строчных букв.

Пример:

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 и делайте это рекурсивно, пока больше не будет соседних узлов. Эта рекурсивная функция будет принимать 2 аргумента, один из которых является узлом Trie, который указывает на текущий посещаемый узел Trie, а другой — строкой, в которой хранится найденная строка с префиксом «str».
Каждый узел Trie хранит логическую переменную 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)

Пользователь будет вводить строку символ за символом, и нам нужно отображать предложения с префиксом, сформированным после каждого введенного символа.
Таким образом, один из подходов к поиску префикса, начинающегося с сформированной строки, состоит в том, чтобы проверить, существует ли префикс в Trie, если да, то вызовите функцию displayContacts (). В этом подходе после каждого введенного символа мы проверяем, существует ли строка в Trie.
Вместо того, чтобы проверять снова и снова, мы можем поддерживать указатель prevNode , который указывает на TrieNode, который соответствует последнему введенному символу пользователем, теперь нам нужно проверить дочерний узел на «prevNode», когда пользователь вводит другой символ, чтобы проверить если он существует в Трие. Если новый префикс отсутствует в Trie, то всю строку, которая формируется путем ввода символов после префикса, также нельзя найти в Trie. Поэтому мы разрываем цикл, который используется для генерации префиксов один за другим, и печатаем «No Result Found» для всех оставшихся символов.

C ++

// C ++ программа для реализации телефона
// Каталог, использующий структуру данных Trie
#include <bits/stdc++.h>

using namespace std;

  

struct TrieNode

{

    // Каждый узел Trie содержит карту child

    // где каждый алфавит указывает на Trie

    // Узел

    // Мы также можем использовать массив фиксированного размера

    // размер 256.

    unordered_map<char,TrieNode*> child;

  

    // isLast истина, если узел представляет

    // конец контакта

    bool isLast;

  

    // Конструктор по умолчанию

    TrieNode()

    {

        // Инициализируем все узлы Trie с NULL

        for (char i = 'a'; i <= 'z'; i++)

            child[i] = NULL;

  

        isLast = false;

    }

};

  
// Сделать корень NULL для простоты, чтобы он не
// должны быть переданы всем функциям.
TrieNode *root = NULL;

  
// Вставить контакт в Trie

void insert(string s)

{

    int len = s.length();

  

    // 'itr' используется для итерации узлов Trie

    TrieNode *itr = root;

    for (int i = 0; i < len; i++)

    {

        // Проверяем, присутствует ли s [i] в

        // Trie

        TrieNode *nextNode = itr->child[s[i]];

        if (nextNode == NULL)

        {

            // Если не найден, создайте новый TrieNode

            nextNode = new TrieNode();

  

            // Вставить в карту

            itr->child[s[i]] = nextNode;

        }

  

        // Переместить итератор ('itr'), чтобы указать на следующее

        // Trie Node

        itr = nextNode;

  

        // Если это последний символ строки 's'

        // затем помечаем 'isLast' как true

        if (i == len - 1)

            itr->isLast = true;

    }

}

  
// Эта функция просто отображает все слова из словаря
// проходя текущий узел Строка 'префикс'
// представляет строку, соответствующую пути из
// корень к curNode.

void displayContactsUtil(TrieNode *curNode, string prefix)

{

    // Проверяем, заканчивается ли строка 'prefix' на этом узле

    // Если да, то отобразить найденную строку

    if (curNode->isLast)

        cout << prefix << endl;

  

    // Находим все смежные узлы к текущему

    // Узел, а затем вызвать функцию рекурсивно

    // Это похоже на выполнение DFS на графике

    for (char i = 'a'; i <= 'z'; i++)

    {

        TrieNode *nextNode = curNode->child[i];

        if (nextNode != NULL)

            displayContactsUtil(nextNode, prefix + (char)i);

    }

}

  
// Отображать предложения после каждого ввода символов
// пользователь для данной строки запроса 'str'

void displayContacts(string str)

{

    TrieNode *prevNode = root;

  

    string prefix = "";

    int len = str.length();

  

    // Показать список контактов для сформированной строки

    // после ввода каждого символа

    int i;

    for (i=0; i<len; i++)

    {

        // 'prefix' сохраняет сформированную строку

        prefix += (char)str[i];

  

        // Получить последний введенный символ

        char lastChar = prefix[i];

  

        // Найти узел, соответствующий последнему

        // символ префикса, на который указывает

        // prevNode of Trie

        TrieNode *curNode = prevNode->child[lastChar];

  

        // Если ничего не найдено, разорвать цикл как

        // префиксов больше не будет.

        if (curNode == NULL)

        {

            cout << "nNo Results Found for "" << prefix

                 << "" n";

            i++;

            break;

        }

  

        // Если присутствует в Trie, то отображать все

        // контакты с заданным префиксом.

        cout << "nSuggestions based on "" << prefix

             << "" are n";

        displayContactsUtil(curNode, prefix);

  

        // Изменить prevNode для следующего префикса

        prevNode = curNode;

    }

  

    // Если поиск префикса не удался, мы печатаем

    // "Не найдено результатов" для всех остальных

    // символы текущей строки запроса "str".

    for (; i<len; i++)

    {

        prefix += (char)str[i];

        cout << "nNo Results Found for "" << prefix

             << "" n";

    }

}

  
// Вставляем все контакты в Trie

void insertIntoTrie(string contacts[],int n)

{

    // Инициализируем корневой узел

    root = new TrieNode();

  

    // Вставляем каждый контакт в три

    for (int i = 0; i < n; i++)

        insert(contacts[i]);

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    // Список контактов пользователя

    string contacts[] = {"gforgeeks" , "geeksquiz"};

  

    // Размер списка контактов

    int n = sizeof(contacts)/sizeof(string);

  

    // Вставить все контакты в Trie

    insertIntoTrie(contacts, n);

  

    string query = "gekk";

  

    // Обратите внимание, что пользователь введет «g», затем «e», поэтому

    // сначала отображаем все строки с префиксом как 'g'

    // а затем все строки с префиксом как 'ge'

    displayContacts(query);

  

    return 0;

}

Джава

// Java-программа для реализации телефона
// Каталог, использующий структуру данных Trie

import java.util.*;

  

class TrieNode

{

    // Каждый узел Trie содержит карту child

    // где каждый алфавит указывает на Trie

    // Узел

    HashMap<Character,TrieNode> child;

  

    // isLast истина, если узел представляет

    // конец контакта

    boolean isLast;

  

    // Конструктор по умолчанию

    public TrieNode()

    {

        child = new HashMap<Character,TrieNode>();

  

        // Инициализируем все узлы Trie с NULL

        for (char i = 'a'; i <= 'z'; i++)

             child.put(i,null);

  

        isLast = false;

    }

}

  

class Trie

{

    TrieNode root;

  

    // Вставляем все контакты в Trie

    public void insertIntoTrie(String contacts[])

    {

        root = new TrieNode();

        int n = contacts.length;

        for (int i = 0; i < n; i++)

        {

            insert(contacts[i]);

        }

    }

  

    // Вставить контакт в Trie

    public void insert(String s)

    {

        int len = s.length();

  

        // 'itr' используется для итерации узлов Trie

        TrieNode itr = root;

        for (int i = 0; i < len; i++)

        {

            // Проверяем, присутствует ли s [i] в

            // Trie

            TrieNode nextNode = itr.child.get(s.charAt(i));

            if (nextNode == null)

            {

                // Если не найден, создайте новый TrieNode

                nextNode = new TrieNode();

  

                // Вставляем в HashMap

                itr.child.put(s.charAt(i),nextNode);

            }

  

            // Переместить итератор ('itr'), чтобы указать на следующее

            // Trie Node

            itr = nextNode;

  

            // Если это последний символ строки 's'

            // затем помечаем 'isLast' как true

            if (i == len - 1)

                itr.isLast = true;

        }

    }

  

    // Эта функция просто отображает все слова из словаря

    // проходя текущий узел Строка 'префикс'

    // представляет строку, соответствующую пути из

    // корень к curNode.

    public void displayContactsUtil(TrieNode curNode,

                                   String prefix)

    {

  

        // Проверяем, заканчивается ли строка 'prefix' на этом узле

        // Если да, то отобразить найденную строку

        if (curNode.isLast)

            System.out.println(prefix);

  

        // Находим все смежные узлы к текущему

        // Узел, а затем вызвать функцию рекурсивно

        // Это похоже на выполнение DFS на графике

        for (char i = 'a'; i <= 'z'; i++)

        {

            TrieNode nextNode = curNode.child.get(i);

            if (nextNode != null)

            {

                displayContactsUtil(nextNode, prefix + i);

            }

        }

    }

  

    // Отображать предложения после каждого ввода символов

    // пользователь для заданной строки 'str'

    void displayContacts(String str)

    {

        TrieNode prevNode = root;

  

        // 'flag' обозначает, была ли введена строка

        // пока присутствует в списке контактов

  

        String prefix = "";

        int len = str.length();

  

        // Показать список контактов для сформированной строки

        // после ввода каждого символа

        int i;

        for (i = 0; i < len; i++)

        {

            // 'str' сохраняет введенную строку

            prefix += str.charAt(i);

  

            // Получить последний введенный символ

            char lastChar = prefix.charAt(i);

  

            // Найти узел, соответствующий последнему

            // символ 'str', на который указывает

            // prevNode of Trie

            TrieNode curNode = prevNode.child.get(lastChar);

  

            // Если ничего не найдено, разорвать цикл как

            // префиксов больше не будет.

            if (curNode == null)

            {

                System.out.println("nNo Results Found for ""

                                          + prefix + """);

                i++;

                break;

            }

  

            // Если присутствует в Trie, то отображать все

            // контакты с заданным префиксом.

            System.out.println("nSuggestions based on ""

                                    + prefix + "" are");

            displayContactsUtil(curNode, prefix);

  

            // Изменить prevNode для следующего префикса

            prevNode = curNode;

        }

  

        for ( ; i < len; i++)

        {

            prefix += str.charAt(i);

            System.out.println("nNo Results Found for ""

                                          + prefix + """);

        }

    }

}

  
// Код драйвера

class Main

{

    public static void main(String args[])

    {

        Trie trie = new Trie();

  

        String contacts [] = {"gforgeeks", "geeksquiz"};

  

        trie.insertIntoTrie(contacts);

  

        String query = "gekk";

  

        // Обратите внимание, что пользователь введет «g», затем «e», поэтому

        // сначала отображаем все строки с префиксом как 'g'

        // а затем все строки с префиксом как 'ge'

        trie.displayContacts(query);

    }

}


Выход:

Suggestions based on "g" are 
geeksquiz
gforgeeks

Suggestions based on "ge" are 
geeksquiz

No Results Found for "gek" 

No Results Found for "gekk" 

Эта статья предоставлена Чирагом Агарвалом . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Реализовать телефонный справочник

0.00 (0%) 0 votes