¿Existe una palabra escondida dentro de una matriz de letras? Resolverlo con DFS recursivo en JavaScript es una de las preguntas clásicas en entrevistas técnicas, y aquí vas a ver cómo construir esa solución paso a paso, decidiendo qué sacrificar entre memoria, espacio y legibilidad.

Este recorrido es útil si estás preparando entrevistas de algoritmos, practicando estructuras de datos sobre matrices o buscando entender cuándo conviene usar backtracking frente a otras alternativas como un hash set de visitados.

¿Cómo se plantea la búsqueda de una palabra en una matriz?

La función wordExists recibe una matriz de letras y una palabra, y debe retornar un booleano. La estrategia parte de una idea simple: recorrer toda la matriz hasta encontrar una casilla cuya letra coincida con la primera letra de la palabra, y desde ahí lanzar una búsqueda en profundidad.

El flujo general queda así [01:00]:

• Inicializa una variable existe = false que será el valor a retornar.
• Itera con dos ciclos anidados sobre filas y columnas de la matriz.
• Cuando matriz[i][j] coincida con palabra[0], llama a la función dfs con esa posición y el índice 0.
• Si después del DFS existe ya es true, retorna inmediatamente sin seguir iterando.

¿Por qué iniciar el DFS solo cuando coincide la primera letra? Porque hacer Depth First Search desde cada casilla sin filtrar es trabajo desperdiciado. Si la primera letra ni siquiera coincide, ese camino nunca va a construir la palabra completa.

¿Cómo funciona el DFS recursivo dentro de la función?

La función dfs se define dentro de wordExists porque solo se usa en ese contexto [03:30]. Recibe la matriz, las coordenadas x, y y un index que indica qué letra de la palabra estamos buscando ahora mismo.

¿Cuál es el caso base de la recursión?

Lo primero que tienes que validar son los bordes de la matriz. Si te mueves con desplazamientos de más uno o menos uno en cada dirección, puedes salirte del arreglo y provocar un error de acceso.

Las condiciones para retornar de inmediato son:

• x < 0 o y < 0.
• x >= matriz.length o y >= matriz[0].length.
• matriz[x][y] !== palabra[index], porque ya sabes que ese camino no construye la palabra.

¿Qué es backtracking en este problema? Es marcar una celda como usada antes de explorar sus vecinos y restaurar su valor original cuando esa rama no funciona, para que esa letra pueda servir en otro camino.

¿Cómo se evita reutilizar la misma celda?

Aquí entra el truco del marcado temporal [05:45]. Cuando confirmas que matriz[x][y] es la letra que buscas, reemplazas ese valor por un carácter imposible como #. Así, si la recursión vuelve a esa misma casilla, la comparación con palabra[index] fallará y no la contarás dos veces.

Un ejemplo concreto: si buscas la palabra casa y estás parado en la primera A, marcas esa celda con #. Cuando intentes encontrar la última A, no podrás reusar la misma posición.

Al terminar de explorar las cuatro direcciones, restauras el valor original con matriz[x][y] = palabra[index]. Ese paso de restauración es la esencia del backtracking.

¿Cuándo declarar que la palabra fue encontrada?

Antes de seguir explorando vecinos, revisa si ya estás en la última letra. Si index + 1 === palabra.length, significa que acabas de hacer match con la N de avión (o la última letra de cualquier palabra), entonces asignas existe = true y retornas.

Si todavía faltan letras, la función llama recursivamente a dfs en las cuatro direcciones con index + 1:

• Arriba: dfs(matriz, x - 1, y, index + 1).
• Abajo: dfs(matriz, x + 1, y, index + 1).
• Izquierda: dfs(matriz, x, y - 1, index + 1).
• Derecha: dfs(matriz, x, y + 1, index + 1).

Una alternativa más elegante, mencionada en clase [08:20], es declarar un arreglo de direcciones [[1,0],[-1,0],[0,1],[0,-1]] y recorrerlo con un for. Funciona igual, pero escala mejor cuando aparecen movimientos más complejos, como los del caballo en ajedrez.

¿Qué decisiones de diseño puedes negociar al resolver este problema?

La parte más valiosa de este ejercicio no es el código, es entender qué estás priorizando. En una entrevista real, la persona que evalúa quiere escucharte razonar sobre trade offs.

Algunas decisiones que puedes discutir:

• Marcar con # vs usar un hash set de visitados: el marcado temporal ahorra memoria porque modifica la matriz en sitio, mientras que el set ocupa espacio extra proporcional al camino explorado.
• DFS escrito cuatro veces vs arreglo de direcciones con for: lo segundo es más mantenible si el problema crece a más direcciones o reglas de movimiento.
• Salir temprano cuando existe es true: evita iteraciones innecesarias sobre el resto de la matriz.

¿Qué priorizar entre tiempo y espacio? Depende del contexto. Si trabajas con matrices pequeñas, la legibilidad gana. Si la entrada son píxeles de una imagen enorme, modificar en sitio y restaurar suele ser más eficiente que mantener estructuras paralelas.

En la clase también se aclara que esta misma pregunta apareció en una entrevista técnica real, y la respuesta correcta no fue solo dar una solución, sino mostrar qué otras opciones existen y por qué se escoge una sobre otra.

¿Cómo resolverías tú este problema? ¿Cambiarías el marcado por un set de visitados, o usarías el arreglo de direcciones desde el inicio? Comparte tu versión y lee las de tus compañeros en los comentarios.