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