[Leetcode] 0211. Diseño de estructura de datos para agregar y buscar palabras

Explore diversas soluciones LeetCode en Python, C++, JavaScript, SQL y TypeScript. Ideal para preparación de entrevistas, aprendizaje y práctica de código en múltiples lenguajes de programación. Enlace de repositorio de Github

Tabla de contenido

Medio

Diseñe una estructura de datos que admita agregar nuevas palabras y descubrir si una cadena coincide con alguna cadena agregada previamente.

Implementar el Diccionario de palabras clase:

Diccionario de palabras() Inicializa el objeto.
void addWord(palabra) Añade palabra Con la estructura de datos se puede hacer coincidir más tarde.
bool búsqueda(palabra) Devoluciones verdadero Si hay alguna cadena en la estructura de datos que coincida palabra o FALSO de lo contrario. palabra puede contener puntos '.' donde los puntos se pueden combinar con cualquier letra.

Ejemplo:

Aporte
["WordDictionary","addWord","addWord","addWord","buscar","buscar","buscar","buscar"] [[],["malo"],["papá"],["enojado"],["almohadilla"],["malo"],[".anuncio"],["b.."]]
Producción
[nulo,nulo,nulo,nulo,falso,verdadero,verdadero,verdadero]

Explicación
WordDictionary wordDictionary = nuevo WordDictionary(); diccionariodepalabras.addWord("malo"); wordDictionary.addWord("papá"); wordDictionary.addWord("loco"); diccionarioDePalabras.search("pad"); // devuelve Falso wordDictionary.search("malo"); // devuelve True wordDictionary.search(".ad"); // devuelve True wordDictionary.search("b.."); // devuelve Verdadero

Restricciones:

1 <= longitud de palabra <= 25
palabra en agregar palabra Consiste en letras minúsculas del alfabeto inglés.
palabra en buscar consistir en '.' o letras minúsculas en inglés.
Habrá como máximo 2 puntos en palabra para buscar consultas.
A lo sumo 10 ⁴ Se realizarán llamadas a agregar palabra y buscar.

Pitón

				
					Complejidad de tiempo #: O(M) Complejidad de espacio #: O(M) clase TrieNode: def __init__(self): self.children = {} self.isEnd = False clase WordDictionary: def __init__(self): self.root = TrieNode() self.maxLen = 0 def addWord(self, palabra: str) -> None: nodo = self.root l = 0 para char en palabra: si char no está en nodo.children: nodo.children[char] = TrieNode() nodo = nodo.children[char] l += 1 self.maxLen = max(self.maxLen, l) nodo.isEnd = True def search(self, palabra: str) -> bool: si len(palabra) > self.maxLen: devuelve False def helper(idx, nodo): para i en rango(idx, len(palabra)): si palabra[i] == ".": para hijo en nodo.hijos.valores(): si ayudante(i + 1, hijo): devuelve Verdadero devuelve Falso de lo contrario: si palabra[i] no está en nodo.hijos: devuelve Falso nodo = nodo.hijos[palabra[i]] devuelve nodo.isEnd devuelve ayudante(0, self.root) diccionarioDePalabras = DiccionarioDePalabras() diccionarioDePalabras.addWord("malo") diccionarioDePalabras.addWord("papá") diccionarioDePalabras.addWord("loco") print(DiccionarioDePalabras.search("almohadilla")) print(DiccionarioDePalabras.search("malo")) print(DiccionarioDePalabras.search(".anuncio")) print(DiccionarioDePalabras.search("b.."))

Medio

Pitón

Artículos relacionados