Este artículo ofrece un análisis completo de la solución al problema LeetCode 211 "Design Add and Search Words Data Structure": desde el enfoque de resolución de problemas y los pasos del algoritmo hasta la complejidad temporal y espacial. Además, resume los casos límite y compara tres soluciones, lo que le ayudará a comprender "Design Add and Search Words Data Structure" de una sola vez.
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
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ñadepalabraCon la estructura de datos se puede hacer coincidir más tarde.bool búsqueda(palabra)DevolucionesverdaderoSi hay alguna cadena en la estructura de datos que coincidapalabraoFALSOde lo contrario.palabrapuede 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 <= 25palabraenagregar palabraConsiste en letras minúsculas del alfabeto inglés.palabraenbuscarconsistir en'.'o letras minúsculas en inglés.- Habrá como máximo
2puntos enpalabraparabuscarconsultas. - A lo sumo
10 4Se realizarán llamadas aagregar palabraybuscar.
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.."))
Ejercicios de extensión de problemas de LeetCode
Se recomienda practicar con otras notas de resolución de problemas de la misma serie:
Diseño, adición y búsqueda de palabras, estructura de datos, enfoque de resolución de problemas
Este problema añade el carácter comodín "." al Trie: cuando se encuentra, no se puede seguir un único camino; hay que probar todos los nodos hijos, por lo que la búsqueda pasa de un bucle a una búsqueda recursiva (o DFS). addWord sigue completamente el enfoque básico del Trie; la diferencia en complejidad reside únicamente en la búsqueda.
Diseño, Agregar y Buscar palabras: Estructura de datos, Pasos del algoritmo
- addWord: Igual que el Trie básico, crea nodos carácter por carácter y marca el punto final como isEnd.
- La función de búsqueda se define como una función recursiva dfs(nodo, índice).
- Si el carácter es una letra normal y no hay un nodo hijo correspondiente, devuelve falso; de lo contrario, regresa recursivamente al siguiente nodo hijo.
- Si el carácter es ".", devuelve recursivamente una vez por cada nodo hijo, devolviendo verdadero si alguno tiene éxito; devuelve node.isEnd cuando se agota el índice.
Diseño, agregar y buscar palabras, estructura de datos, análisis de complejidad
| proyecto | Complejidad |
|---|---|
| complejidad temporal | O(L) ~ O(26^L) |
| Complejidad espacial | O(N·L) |
Sin caracteres comodín, la complejidad temporal es O(L), la misma que la de un Trie convencional; en el peor de los casos, donde todos los caracteres son ".", todas las ramas deben expandirse, con un límite superior de O(2^L). En la práctica, el diccionario es disperso y las ramas se podan rápidamente. La complejidad espacial es O(N·L) para el propio Trie más la profundidad de recursión O(L).
Casos límite y errores comunes en la estructura de datos de agregar y buscar palabras de diseño
- “La rama "." itera sobre los nodos hijos existentes, en lugar de intentar resolver las 26 letras.
- Cuando el índice llega al final, debe comprobar isEnd; de lo contrario, el prefijo se interpretará erróneamente como una sola palabra.
- Una consulta que consiste enteramente en "." es equivalente a preguntar "¿Existe una palabra de longitud L?".
- Al consultar un gran número de caracteres universales, se puede utilizar la agrupación por longitud para acelerar el proceso.
Diseño, agregar y buscar palabras, estructura de datos, comparación con otras soluciones.
| solución | tiempo | espacio | ilustrar |
|---|---|---|---|
| Almacena todas las palabras en un conjunto y compáralas usando expresiones regulares. | O(N·L) | O(N·L) | Cada consulta requiere escanear todas las palabras. |
| Tras agruparlos por longitud, compárelos uno por uno. | O(N·L) | O(N·L) | Se realiza un recorte, pero sigue siendo un escaneo lineal. |
| Prueba + DFS de carácter universal | O(L)~O(26^L) | O(N·L) | Este artículo adopta |
