Requisito previo: Trie | (Insertar y Buscar)
Dada una array de strings palabras[] y una string parcial str , la tarea es encontrar las strings de la forma dada str a partir de la array de string dada.
Una string parcial es una string a la que le faltan algunos caracteres. Por ejemplo: “..ta” es una string de longitud 4 que termina en “ta” y tiene dos caracteres faltantes en el índice 0 y 1 .
Ejemplos:
Entrada: palabras[] = [“luna”, “pronto”, “mes”, “fecha”, “datos”], str = “..en”
Salida: [“luna”, “pronto”]
Explicación:
“luna ” y “pronto” coincide con la string parcial dada “..en”Entrada: palabras[] = [“fecha”, “datos”, “mes”], str = “dt”
Salida: [“fecha”, “datos”]
Explicación:
“fecha” y “datos” coinciden con la string parcial dada «dt»
Acercarse:
Estructura de un Node Trie: La idea es usar Trie para resolver el problema dado A continuación se muestran los pasos y estructuras del trie:
struct TrieNode
{
struct TrieNode* children[26];
bool endOfWord;
};
La siguiente imagen explica la construcción de trie usando las teclas dadas en el ejemplo anterior
root
/ | \
d m s
| | |
a o o
| | \ |
t o n o
/ | | | |
t
|
Cada Node es un TrieNode con enlaces de puntero a los hijos subsiguientes de acuerdo con la palabra agregada. Los valores en otras posiciones del puntero donde no hay caracteres presentes se marcan con NULL. endOfWord están representados por color azul o Nodes de hoja.
Pasos:
- Inserte todas las palabras disponibles en la estructura trie utilizando el método addWord() .
- Cada carácter de la palabra que se agregará se inserta como un TrieNode individual. La array de niños es una array de 26 punteros TrieNode.
- Cada índice representa un carácter del alfabeto inglés. Si se agrega una nueva palabra, entonces para cada carácter, se debe verificar si existe el puntero TrieNode para ese alfabeto, luego continuar con el siguiente carácter, si no, se crea un nuevo TrieNode y se hace que el puntero señale este nuevo Node. y el proceso se repite para el siguiente carácter en este nuevo Node. endOfWord se hace verdadero para el TrieNode apuntado por el puntero TrieNode del último carácter.
- Para buscar la clave, verifique la presencia de TrieNode en el índice marcado por el carácter. Si está presente, bajamos la rama y repetimos el proceso para el siguiente personaje. De manera similar, buscar la string parcial si un ‘.’ se encuentra, buscamos todos los punteros TrieNode disponibles en la array de niños y continuamos con cada carácter, identificado por un índice, ocupando la posición de ‘.’ una vez.
- Si la ubicación del puntero está vacía en algún punto, devolvemos no encontrado. De lo contrario, verifique endOfWord en el último TrieNode, si es falso, devolvemos no encontrado, de lo contrario, se encuentra la palabra.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Dictionary Class
class Dictionary {
public:
// Initialize your data structure
Dictionary* children[26];
bool endOfWord;
// Constructor
Dictionary()
{
this->endOfWord = false;
for (int i = 0; i < 26; i++) {
this->children[i] = NULL;
}
}
// Adds a word into a data structure
void addWord(string word)
{
// Crawl pointer points the object
// in reference
Dictionary* pCrawl = this;
// Traverse the given array of words
for (int i = 0; i < word.length(); i++) {
int index = word[i] - 'a';
if (!pCrawl->children[index])
pCrawl->children[index]
= new Dictionary();
pCrawl = pCrawl->children[index];
}
pCrawl->endOfWord = true;
}
// Function that returns if the word
// is in the data structure or not
// A word can contain a dot character '.'
// to represent any one letter
void search(string word, bool& found,
string curr_found = "",
int pos = 0)
{
Dictionary* pCrawl = this;
if (pos == word.length()) {
if (pCrawl->endOfWord) {
cout << "Found: "
<< curr_found << "\n";
found = true;
}
return;
}
if (word[pos] == '.') {
// Iterate over every letter and
// proceed further by replacing
// the character in place of '.'
for (int i = 0; i < 26; i++) {
if (pCrawl->children[i]) {
pCrawl
->children[i]
->search(word,
found,
curr_found + char('a' + i),
pos + 1);
}
}
}
else {
// Check if pointer at character
// position is available,
// then proceed
if (pCrawl->children[word[pos] - 'a']) {
pCrawl
->children[word[pos] - 'a']
->search(word,
found,
curr_found + word[pos],
pos + 1);
}
}
return;
}
// Utility function for search operation
void searchUtil(string word)
{
Dictionary* pCrawl = this;
cout << "\nSearching for \""
<< word << "\"\n";
bool found = false;
pCrawl->search(word, found);
if (!found)
cout << "No Word Found...!!\n";
}
};
// Function that search the given pattern
void searchPattern(string arr[], int N,
string str)
{
// Object of the class Dictionary
Dictionary* obj = new Dictionary();
for (int i = 0; i < N; i++) {
obj->addWord(arr[i]);
}
// Search pattern
obj->searchUtil(str);
}
// Driver Code
int main()
{
// Given an array of words
string arr[] = { "data", "date", "month" };
int N = 3;
// Given pattern
string str = "d.t.";
// Function Call
searchPattern(arr, N, str);
}
Searching for "d.t." Found: data Found: date
Complejidad de tiempo: O(M*log(N)), donde N es el número de strings y M es la longitud del patrón dado
Espacio auxiliar: O(26*M)
Publicación traducida automáticamente
Artículo escrito por chitrankmishra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA