Búsqueda de Palabras en Matrices usando Backtracking y DFS

¿Cómo resolver el problema de búsqueda de palabras en matrices?

En esta clase abordaremos un problema interesante en programación: la búsqueda de palabras en matrices. Imagina un tablero lleno de letras, de las cuales debes determinar si una palabra está formada por letras adyacentes. Es un desafío que puede parecer similar a un crucigrama, pero aquí las palabras pueden formarse en cualquier dirección adyacente, no solo en líneas horizontales o verticales. Esto hace más complejo el proceso, pero, precisamente, es lo que lo hace interesante. ¡Explorémoslo!

¿Qué técnicas podemos usar para resolverlo?

Para enfrentar este desafío, nos apoyaremos principalmente en dos técnicas fundamentales de programación: el DFS (Depth First Search) o búsqueda en profundidad, y el backtracking.

1. DFS (Depth First Search): Ayuda a explorar todos los posibles caminos en la matriz para formar la palabra. A medida que avanzamos por cada letra, podríamos profundizar en diferentes caminos, verificando cada letra adyacente para continuar o descartar un camino si deja de coincidir con la palabra que buscamos.

2. Backtracking: Esto nos permite "deshacer" nuestros pasos cuando un camino no lleva al resultado deseado. Al retroceder, evaluamos otros caminos posibles sin tener que empezar desde cero nuevamente.

¿Cómo podemos definir direcciones adyacentes?

Al enfrentar este problema, determinar las direcciones consideradas adyacentes es crucial. Normalmente consideraríamos:

• Adyacentes horizontales (izquierda y derecha).
• Adyacentes verticales (arriba y abajo).
• Cámara diagonal, en caso de que se permita en la especificación.

Saber qué direcciones son válidas nos ayuda a decidir los siguientes pasos cuando estamos en un nodo o letra actual.

¿Cómo evitamos reutilizar las mismas letras?

Un aspecto importante en la búsqueda de palabras es asegurar que una misma letra no se use más de una vez en la formación de una palabra. Esto se podría gestionar de diferentes maneras:

1. Marcado de letras usadas: Se puede usar una lista o conjunto que registre las letras utilizadas hasta el momento. Sin embargo, esta opción puede ser costosa en términos de espacio.

2. Reemplazo temporal de caracteres: Una solución más eficiente es reemplazar temporalmente una letra utilizada con un carácter que sabemos que no formará parte de ninguna palabra, como un numeral (#). Esto permite marcar una letra como en uso sin reservar espacio adicional.

   # Ejemplo de implementación en Python
   def buscar_palabra(matriz, palabra):
       def dfs(x, y, índice):
           if índice == len(palabra):
               return True
           if (x < 0 or x >= len(matriz) or y < 0 or y >= len(matriz[0]) or
               matriz[x][y] != palabra[índice]):
               return False
           tmp, matriz[x][y] = matriz[x][y], '#'
           resultado = (dfs(x+1, y, índice+1) or dfs(x-1, y, índice+1) or 
                        dfs(x, y+1, índice+1) or dfs(x, y-1, índice+1))
           matriz[x][y] = tmp
           return resultado
   
       for i in range(len(matriz)):
           for j in range(len(matriz[0])):
               if dfs(i, j, 0):
                   return True
       return False
   

En este código, utilizamos DFS para recorrer la matriz, reemplazando temporalmente las letras utilizadas con # y restaurando su valor original al retroceder. Este método permite gestionar con eficiencia el marcado de letras utilizadas sin requerir estructuras de datos adicionales.

¿Qué hacer si la palabra no está?

Finalmente, si todas las exploraciones en la matriz no logran formar la palabra, retornamos falso. En el peor de los casos, recorremos toda la matriz, lo que hace que la complejidad temporal sea (O(n^2)), donde n es el número de elementos en la matriz.

Esperamos que esta explicación te haya dado una buena perspectiva sobre cómo resolver el problema de búsqueda de palabras en matrices. Es un tema que involucra conceptos clave en algoritmos que pueden aplicarse a una variedad de problemas. Te animamos a experimentar y encontrar tus propias soluciones innovadoras. ¡Hasta la próxima lección!