Word Search II: trie y retroceso en una cuadrícula

Word Search II (LeetCode 212): dado un tablero de caracteres m × n y una lista de palabras, encuentre todas las palabras que se puedan formar mediante celdas adyacentes consecutivas (horizontal o verticalmente), donde cada celda solo se puede utilizar una vez. Esto es más difícil que Word Search I (una sola palabra), porque necesitamos encontrar todas las palabras coincidentes simultáneamente; ejecutar Word Search I de forma ingenua para cada palabra tiene un coste de O(W × m × n × 4^L), que es demasiado lento.

Insertar todas las palabras objetivo en un trie y después ejecutar un DFS con backtracking sobre el tablero permite buscar todas las palabras simultáneamente. En cada celda del tablero, en lugar de comprobar «¿esta ruta forma mi palabra objetivo?», comprobamos «¿esta ruta coincide con un prefijo del trie?». En cuanto un prefijo del trie deja de coincidir, podamos toda la rama del DFS, lo que evita trabajo redundante entre todas las palabras que comparten ese prefijo.

Inserte todas las palabras en un trie. Almacene la palabra completa en el nodo hoja (en node.word) en lugar de guardar únicamente un booleano, de modo que, cuando se encuentre una coincidencia completa durante el backtracking, podamos añadir inmediatamente la palabra a los resultados sin reconstruirla carácter por carácter.

Inicie un DFS desde cada celda del tablero. En cada paso: (1) compruebe si el carácter de la celda actual existe como hijo del nodo actual del trie; (2) si existe, marque la celda como visitada (asígnеле un marcador como '#') y haga una llamada recursiva para las 4 celdas vecinas; (3) después de la recursión, restaure la celda (quite la marca). Cuando un nodo del trie tenga un word distinto de None, añádalo a los resultados y establézcalo en None para evitar duplicados.

Tiempo: O(m × n × 4^L), donde L es la longitud máxima de las palabras. Para cada una de las m×n celdas iniciales, el DFS explora hasta 4^L rutas. El trie poda las rutas que no coinciden con ningún prefijo de palabra, por lo que en la práctica es mucho más rápido. Construir el trie cuesta O(W × L), donde W es el número de palabras. Espacio: O(W × L) para el trie, más una profundidad O(L) de la pila de recursión.

Después de encontrar una palabra, elimine el nodo hoja del trie (no se limite a establecer la palabra en null) si no tiene hijos. Esto evita volver a visitar ramas muertas en llamadas posteriores del DFS. Cuando los hijos de un nodo queden vacíos después de encontrar la palabra, elimínelo del diccionario children de su padre. Esta optimización es importante cuando muchas palabras comparten prefijos largos.

Almacenar la palabra completa en el nodo hoja del trie (en lugar de reconstruirla a partir de la ruta del DFS) ofrece dos ventajas: (1) recuperar la palabra en O(1) cuando se encuentra una coincidencia, en lugar de reconstruir la ruta en O(L); (2) establecer node.word = None después de encontrar la palabra proporciona una deduplicación limpia en O(1), sin necesidad de un conjunto de resultados independiente. En Word Search II, en particular, evitar duplicados es importante porque, en teoría, la misma palabra podría encontrarse siguiendo rutas diferentes.

En lugar de utilizar un conjunto visited independiente (que requeriría un espacio O(m × n) por ruta del DFS), marque las celdas directamente en el tablero reemplazando su carácter por un marcador como '#'. Cuando termine el DFS, restaure el carácter original. Esta técnica: (1) utiliza un espacio adicional O(1) por celda; (2) evita automáticamente volver a visitar una celda dentro de una misma ruta; (3) es completamente transparente para el recorrido del trie, ya que '#' nunca estará en el trie.

Casos límite importantes: (1) palabras duplicadas en la lista de palabras: almacénelas en un conjunto o utilice la técnica node.word = None para evitar duplicados en los resultados; (2) palabras muy largas que superan las dimensiones del tablero: no se pueden formar, pero el DFS lo gestiona de forma natural al quedarse sin celdas adyacentes; (3) tablero de una sola celda: solo se pueden encontrar palabras de un carácter; (4) una misma palabra se puede encontrar mediante rutas diferentes: la técnica node.word = None evita contarla dos veces.

Enfoque ingenuo: para cada una de las W palabras, ejecute Word Search I: O(W × m × n × 4^L). Con el trie, todas las palabras se buscan simultáneamente: O(m × n × 4^L), independientemente de W. Para W=1000 palabras de longitud 10 en un tablero de 10×10, el enfoque ingenuo es 1000 veces más lento que el trie. El trie actúa como un filtro de prefijos compartido que amortiza el coste entre todas las palabras: un ejemplo clásico de cómo utilizar una estructura de datos para lograr una mejora asintótica.

Solución completa de Word Search II: construya un trie con las palabras y almacene la cadena de la palabra en la hoja. Para cada celda del tablero, ejecute un DFS: compruebe si el carácter actual existe en el nodo actual del trie, marque la celda como '#', haga llamadas recursivas para las 4 celdas vecinas y restaure la celda. Cuando node.word no sea null, añádalo a los resultados y establézcalo en null. Opcionalmente, pode las ramas vacías del trie después de utilizarlas. Devuelva la lista de resultados. Tiempo: O(m×n×4^L); espacio: trie O(W×L) + recursión O(L).

Ponga a prueba su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.

En esta lección aprendió: Word Search II utiliza un trie para permitir la búsqueda simultánea de varias palabras con poda de prefijos compartidos, almacenar la cadena de la palabra en la hoja del trie permite recuperarla en O(1) y deduplicarla fácilmente estableciéndola en None después de encontrarla, y marcar las celdas visitadas directamente en el tablero con '#' evita utilizar un espacio adicional O(m×n) por ruta del DFS. Con esto termina el curso Tries and String Algorithms: ha aprendido a dominar una de las estructuras de datos específicas para cadenas más potentes y utilizadas en entrevistas.