Как реализовать функцию автозаполнения текста с помощью троичного дерева поиска

Опубликовано: 1 Января, 2022

Для данного набора строк S и строки patt задача состоит в том, чтобы автоматически дополнить строку patt строками из S , имеющими в качестве префикса patt , с использованием троичного дерева поиска. Если ни одна строка не соответствует данному префиксу, выведите «Нет» .

Примеры:

Input: S = {“wallstreet”, “geeksforgeeks”, “wallmart”, “walmart”, “waldomort”, “word”],
patt = “wall”
Output:
wallstreet
wallmart
Explanation:
Only two strings {“wallstreet”, “wallmart”} from S matches with the given pattern “wall”.
Input: S = {“word”, “wallstreet”, “wall”, “wallmart”, “walmart”, “waldo”, “won”}, patt = “geeks”
Output: None
Explanation:
Since none of word of set matches with pattern so empty list will be printed.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход Trie: обратитесь к этой статье, чтобы узнать о реализации с использованием структуры данных Trie.

Подход с использованием троичного дерева поиска Для решения проблемы выполните следующие действия:

Вставьте все символы строк в S в троичное дерево поиска на основе следующих условий:
1. Если вставляемый символ меньше текущего значения узла, пройти по левому поддереву.
2. Если символ, который нужно вставить, больше, чем текущее значение узла, перейти к правому поддереву.
3. Если вставляемый символ совпадает с символом текущего значения узла, пройти по равному поддереву, если оно не является концом слова. Если да, отметьте узел как конец слова.
Используйте аналогичный подход для извлечения предложений.
Пройдите по дереву, чтобы найти заданный шаблон префикса, следуя той же методике обхода, которая упоминалась выше.
Если данный префикс не найден, выведите «Нет».
Если данный префикс найден, перейдите по дереву от узла, на котором префикс заканчивается. Пройдите по левому поддереву и сгенерируйте предложения, за которыми следуют правые и равные поддеревья из каждого узла.
Каждый раз, когда встречается узел, для которого установлена переменная endofWord , это означает, что предложение было получено. Изложите это предложение словами .
Верните слова после генерации всех возможных предложений.

Ниже представлена реализация описанного выше подхода:

C ++

 // C++ Program to generate
 // autocompleted texts from
 // a given prefix using a
 // Ternary Search Tree
 #include <bits/stdc++.h>
 using namespace std;
 
// Define the Node of the
 // tree
 struct Node {
 
    // Store the character
    // of a string
    data; char
    // Store the end of
    // word
    int end;
    // Left Subtree
    struct Node* left;
 
    // Equal Subtree
    struct Node* eq;
 
    // Right Subtree
    struct Node* right;
 };
 
// Function to create a Node
 Node* createNode( char newData)
 {
    struct Node* newNode = new Node();
    newNode->data = newData;
    newNode->end = 0;
    newNode->left = NULL;
    newNode->eq = NULL;
    newNode->right = NULL;
    return newNode;
 }
 
// Function to insert a word
 // in the tree
 void insert(Node** root,
            string word,
            int pos = 0)
 {
 
    // Base case
    if (!(*root))
        *root = createNode(word[pos]);
 
    // If the current character is
    // less than root's data, then
    // it is inserted in the
    // left subtree
 
    if ((*root)->data > word[pos])
        insert(&((*root)->left), word,
               pos);
 
    // If current character is
    // more than root's data, then
    // it is inserted in the right
    // subtree
 
    else if ((*root)->data < word[pos])
        insert(&((*root)->right), word,
               pos);
 
    // If current character is same
    // as that of the root's data
 
    else {
        // If it is the end of word
 
        if (pos + 1 == word.size())
            // Mark it as the
            // end of word
            (*root)->end = 1;
 
        // If it is not the end of
        // the string, then the
        // current character is
        // inserted in the equal subtree
 
        else
            insert(&((*root)->eq), word, pos + 1);
    }
 }
 
// Function to traverse the ternary search tree
 void traverse(Node* root,
              vector<string>& ret,
              char * buff,
              int depth = 0)
 {
    // Base case
    if (!root)
        return ;
    // The left subtree is
    // traversed first
    traverse(root->left, ret,
             buff, depth);
 
    // Store the current character
    buff[depth] = root->data;
 
    // If the end of the string
    // is detected, store it in
    // the final ans
    if (root->end) {
        buff[depth + 1] = '' ;
        ret.push_back(string(buff));
    }
 
    // Traverse the equal subtree
    traverse(root->eq, ret,
             buff, depth + 1);
 
    // Traverse the right subtree
    traverse(root->right, ret,
             buff, depth);
 }
 
// Utility function to find
 // all the words
 vector<string> util(Node* root,
                    string pattern)
 {
    // Stores the words
    // to suggest
    char buffer[1001];
 
    vector<string> ret;
 
    traverse(root, ret, buffer);
 
    if (root->end == 1)
        ret.push_back(pattern);
    return ret;
 }
 
// Function to autocomplete
 // based on the given prefix
 // and return the suggestions
 vector<string> autocomplete(Node* root,
                            string pattern)
 {
    vector<string> words;
    int pos = 0;
 
    // If pattern is empty
    // return an empty list
    if (pattern.empty())
        return words;
 
    // Iterating over the characters
    // of the pattern and find it's
    // corresponding node in the tree
 
    while (root && pos < pattern.length()) {
 
        // If current character is smaller
        if (root->data > pattern[pos])
            // Search the left subtree
            root = root->left;
 
        // current character is greater
        else if (root->data < pattern[pos])
            // Search right subtree
            root = root->right;
 
        // If current character is equal
        else if (root->data == pattern[pos])
            // Search equal subtree
            root = root->eq;
 
        // If not found
        else
            return words;
 
        pos++;
    }
 
    // Search for all the words
    // from the current node
    words = util(root, pattern);
 
    return words;
 }
 
// Function to print
 // suggested words
 
void print(vector<string> sugg,
           string pat)
 {
    for ( int i = 0; i < sugg.size();
         i++)
        cout << pat << sugg[i].c_str()
             << "
" ;
 }
 
// Driver Code
 int main()
 {
    vector<string> S
        = { "wallstreet" , "geeksforgeeks" ,
            "wallmart" , "walmart" ,
            "waldormort" , "word" };
 
    Node* tree = NULL;
 
    // Insert the words in the
    // Ternary Search Tree
    for (string str : S)
        insert(&tree, str);
 
    string pat = "wall" ;
 
    vector<string> sugg
        = autocomplete(tree, pat);
 
    if (sugg.size() == 0)
        cout << "None" ;
 
    else
        print(sugg, pat);
 
    return 0;
 }

Выход:

Wall Mart
Wallstreet

Сложность времени: O (L * log N), где L - длина самого длинного слова.
Пространство пропорционально длине сохраняемой строки.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Олимпиады по программированию Алгоритмы Структуры данных

Как реализовать функцию автозаполнения текста с помощью троичного дерева поиска

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

C ++

РЕКОМЕНДУЕМЫЕ СТАТЬИ