Buscar una palabra dentro de una matriz de letras parece una sopa de letras, pero con un giro: la palabra puede formarse por cualquier camino de letras adyacentes, no solo en línea recta. Aquí verás cómo plantear Word Search usando DFS y backtracking, qué subproblemas debes resolver y cómo optimizar el manejo de letras visitadas sin gastar memoria extra.

¿Qué pide el problema Word Search?

Recibes una matriz de letras minúsculas del abecedario y una palabra. Tu función debe retornar verdadero si existe un camino de letras adyacentes que forme la palabra, o falso si no existe.

La clave está en cómo defines adyacente. En este planteamiento, dos letras son adyacentes si están conectadas por arriba, abajo, izquierda o derecha. Cada celda funciona como un nodo, y los nodos vecinos son las casillas contiguas.

¿Qué significa que una palabra esté en la matriz? Significa que existe una secuencia de celdas vecinas, sin repetir ninguna, cuyas letras leídas en orden forman la palabra buscada.

Por ejemplo, si buscas la palabra café en una matriz, debes poder trazar un camino C → A → F → É donde cada letra esté pegada a la anterior. Si buscas amor y no existe ese recorrido, retornas falso.

¿Por qué usar DFS y backtracking aquí?

Como necesitas explorar todos los caminos posibles desde cada celda, la herramienta natural es Depth First Search combinada con backtracking. Profundizas mientras la palabra siga apareciendo, y retrocedes cuando el camino deja de servir [02:15].

La idea es así: empiezas en una celda que coincida con la primera letra. Avanzas a una vecina que coincida con la segunda. Si en algún punto ninguna vecina sirve, no descartas todo el recorrido, solo retrocedes un paso y pruebas otra dirección.

• Si encuentras un camino completo que forma la palabra, retornas verdadero.
• Si agotas todas las direcciones desde una celda, retrocedes a la celda anterior.
• Si exploras toda la matriz sin éxito, retornas falso.

Esto evita reiniciar desde cero cada vez. Y aquí viene lo interesante: el backtracking no solo te ahorra trabajo, también te obliga a deshacer el estado cuando regresas, para que las letras puedan reutilizarse en otros caminos.

¿Cómo marcas las letras ya visitadas sin gastar memoria?

Una regla del problema es que no puedes usar la misma celda dos veces dentro de la misma palabra. Si buscas cama y solo tienes una A disponible, no puedes volver a esa A para cerrar la palabra.

La primera idea que aparece es guardar las posiciones visitadas en una lista o un set. Funciona, pero ocupa espacio que tal vez no necesitas.

¿Cómo evitas usar memoria extra para marcar visitados? Reemplazas temporalmente la letra de la celda por un carácter que sabes que no aparece en palabras válidas, como un numeral. Cuando retrocedes, restauras la letra original.

El truco entonces es este: cuando entras a una celda, guardas su letra en una variable, la sustituyes por un carácter especial como #, y sigues la recursión. Al salir de esa rama, antes de retornar, devuelves la letra original a su posición [05:50].

¿Qué subproblemas debes resolver?

Antes de codificar, conviene partir el problema en piezas pequeñas:

1. Definir las direcciones adyacentes que vas a considerar.
2. Iterar cada celda de la matriz como punto de partida.
3. Hacer DFS recursivo desde una celda comparando contra la letra esperada de la palabra.
4. Marcar la celda actual como visitada con un carácter especial.
5. Restaurar la celda original al volver del backtracking.
6. Cortar la recursión cuando completas la palabra o cuando no hay vecinas válidas.

¿Cuál es la complejidad del algoritmo?

En el peor caso, la palabra no está en la matriz y terminas recorriendo todas las celdas explorando caminos. Eso te da una complejidad de O(n²) sobre el tamaño del tablero, sin agregar costo extra por estructuras de datos auxiliares, porque el marcado se hace sobre la misma matriz [06:40].

Esta solución combina tres ideas que vale la pena tener claras:

• DFS para profundizar por cada camino candidato.
• Backtracking para retroceder cuando un camino deja de servir.
• Reemplazo de carácter como técnica para marcar visitados sin memoria adicional.

Antes de ver la implementación, intenta escribir tu propia versión. ¿Cómo modelarías las direcciones? ¿Usarías un set de visitados o el truco del carácter especial? Comparte tu solución en los comentarios y nos vemos en la siguiente clase.