Encontrar una palabra dentro de una matriz de caracteres es uno de los problemas clásicos que aparecen en entrevistas técnicas de grandes empresas de tecnología. Comprender cómo funciona la búsqueda secuencial sobre celdas adyacentes es fundamental para resolverlo con confianza y claridad.
¿En qué consiste el problema Word Search?
El planteamiento es directo: se recibe un tablero (una matriz M por N de caracteres) y una palabra (una cadena de caracteres). El objetivo es retornar true o false dependiendo de si la palabra puede encontrarse dentro del tablero [0:28].
Pero no basta con que las letras existan en cualquier lugar de la matriz. La palabra debe poder construirse a partir de celdas secuencialmente adyacentes [0:55]. Esto significa que cada letra siguiente debe estar justo al lado de la anterior: arriba, abajo, izquierda o derecha.
¿Qué significa "secuencialmente adyacente"?
Si necesitas formar la palabra y la primera letra es una A, la segunda letra (por ejemplo, una B) debe estar en una celda vecina de esa A [1:02]. Si la B está en otro punto lejano del tablero, no sirve. Cada letra de la palabra debe encontrarse pegada a la anterior, formando un camino continuo.
¿Por qué no se puede reutilizar una celda?
Otra restricción importante es que la misma celda no puede ser utilizada más de una vez durante la construcción de la palabra [1:22]. Por ejemplo, si necesitas la palabra "casa" y ya usaste una celda con la letra A, no puedes regresar a esa misma celda para la segunda A. Necesitas encontrar una A diferente en otra posición del tablero.
¿Cómo se ve un ejemplo resuelto?
En el ejemplo presentado, se recibe una matriz y la palabra ABCCED [1:42]. El resultado es true porque:
- Se empieza en la celda con la A.
- Al lado está la B.
- Al lado de la B está la primera C.
- Debajo de esa C está la segunda C.
- Debajo de esa segunda C está la E.
- Y al lado de la E está la D [1:50].
Todas las letras están una al lado de la otra, formando un camino válido dentro del tablero. No se repite ninguna celda y cada paso es hacia una celda adyacente.
¿Qué considerar antes de diseñar la solución?
Antes de escribir código, vale la pena reflexionar sobre varios puntos:
- Casos borde: ¿qué pasa si la palabra es más larga que el total de celdas? ¿Qué ocurre si el tablero es de 1x1? ¿Y si la palabra está vacía?
- Complejidad temporal: la búsqueda involucra recorrer el tablero y, desde cada celda, explorar caminos posibles. Esto sugiere un enfoque de backtracking, donde se prueban rutas y se retrocede cuando no funcionan.
- Complejidad espacial: se necesita algún mecanismo para marcar las celdas visitadas y evitar reutilizarlas dentro del mismo camino.
El concepto de backtracking es clave aquí. Se trata de una técnica de búsqueda exhaustiva donde se avanza paso a paso, y si un camino no lleva a la solución, se deshace el último paso y se prueba otra dirección. Es la herramienta natural para problemas donde hay que explorar múltiples combinaciones respetando restricciones.
Establecer una meta de complejidad antes de programar ayuda a evaluar si la solución diseñada es eficiente o si necesita optimización. Pensar en el peor caso —donde cada celda inicia una búsqueda que recorre todo el tablero— permite dimensionar el costo real del algoritmo.
¿Qué casos raros se te ocurren para este problema? ¿Cuál crees que sería la complejidad ideal? Comparte tu análisis en los comentarios.
