Tutorial de resolución de problemas de estructuras de datos: Diseño, adición y búsqueda de palabras: Comparación completa de 3 soluciones | Mejores prácticas de LeetCode 211

Tutorial de resolución de problemas de estructura de datos: Diseño, adición y búsqueda de palabras | LeetCode 211

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ñ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 4 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.."))
				
			

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

  1. addWord: Igual que el Trie básico, crea nodos carácter por carácter y marca el punto final como isEnd.
  2. La función de búsqueda se define como una función recursiva dfs(nodo, índice).
  3. 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.
  4. 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

proyectoComplejidad
complejidad temporalO(L) ~ O(26^L)
Complejidad espacialO(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óntiempoespacioilustrar
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 universalO(L)~O(26^L)O(N·L)Este artículo adopta