Dado un conjunto de strings S y una string patt , la tarea es autocompletar la string patt con las strings de S que tienen patt como prefijo, utilizando un árbol de búsqueda ternario . Si ninguna string coincide con el prefijo dado, imprima «Ninguno» .
Ejemplos:
Entrada: S = {“wallstreet”, “geeksforgeeks”, “wallmart”, “walmart”, “waldomort”, “word”],
patt = “wall”
Salida:
wallstreet
wallmart
Explicación:
Solo dos strings {“wallstreet”, “ wallmart”} de S coincide con el patrón dado “wall”.
Entrada: S = {“word”, “wallstreet”, “wall”, “wallmart”, “walmart”, “waldo”, “won”}, patt = “geeks”
Salida: Ninguno
Explicación:
Dado que ninguno de word of set coincide con el patrón, por lo que se imprimirá una lista vacía.
Enfoque Trie: consulte este artículo para obtener información sobre la implementación mediante la estructura de datos Trie . Enfoque del
árbol de búsqueda ternario Siga los pasos a continuación para resolver el problema:
- Inserte todos los caracteres de las strings en S en el árbol de búsqueda ternario según las siguientes condiciones:
- Si el carácter que se va a insertar es más pequeño que el valor del Node actual, recorra el subárbol izquierdo.
- Si el carácter que se va a insertar es mayor que el valor del Node actual, recorra el subárbol derecho hasta.
- Si el carácter que se va a insertar es el mismo que el del valor del Node actual, recorra el subárbol igual si no es el final de la palabra. Si es así, marque el Node como el final de la palabra.
- Siga un enfoque similar para extraer sugerencias.
- Atraviese el árbol para buscar el prefijo patt dado siguiendo una técnica de recorrido similar a la mencionada anteriormente.
- Si no se encuentra el prefijo proporcionado, imprima «Ninguno».
- Si se encuentra el prefijo dado, recorra el árbol desde el Node donde termina el prefijo. Atraviese el subárbol izquierdo y genere sugerencias seguidas por los subárboles derecho e igual de cada Node.
- Cada vez que se encuentra un Node que tiene establecida la variable endofWord , indica que se ha obtenido una sugerencia. Inserte esa sugerencia en palabras .
- Devuelve palabras después de generar todas las sugerencias posibles.
A continuación se muestra la implementación del enfoque anterior:
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 char data; // 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] = '\0'; 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 // since character is found, move to the next character in the pattern root = root->eq; pos++; } // If not found else return words; } // 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() << "\n"; } // 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; }
wallmart wallstreet
Complejidad de tiempo: O(L* log N) donde L es la longitud de la palabra más larga.
El espacio es proporcional a la longitud de la string a almacenar.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por thesyncoder y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA