Implementación de búsqueda de palabras en matrices con DFS en JavaScript

¿Cómo implementar la función para verificar la existencia de una palabra en una matriz?

En esta clase, vamos a implementar una función en JavaScript que nos permitirá verificar si una palabra existe dentro de una matriz de caracteres. Esta es una técnica muy útil en el análisis de datos y manipulación de estructuras complejas. Comencemos entendiendo el proceso y las decisiones clave que se deben tomar al diseñar este tipo de algoritmos.

¿Cuál es el propósito de la función wordExists?

La función wordExists tiene el objetivo de recibir una matriz (un tablero de caracteres) y una palabra, y devolver si dicha palabra se encuentra representada en la matriz. Para esto, mantenemos un enfoque iterativo y recursivo, utilizando una búsqueda en profundidad (Depth-First Search, DFS) para analizar las posibles rutas de la palabra en la matriz.

function wordExists(matrix, word) {
  let existe = false; // Variable booleana que almacenará si la palabra existe
  for (let i = 0; i < matrix.length; i++) { // Recorremos filas
    for (let j = 0; j < matrix[i].length; j++) { // Recorremos columnas
      if (matrix[i][j] === word[0]) { // Si encontramos coincidencia con la primera letra
        // Iniciamos búsqueda DFS a partir de esta posición
        if (dfs(matrix, i, j, 0)) existe = true; 
      }
      if (existe) return true; // Si existe, detenemos la búsqueda
    }
  }
  return false;
}

¿Cómo se implementa la búsqueda en profundidad (DFS)?

La técnica DFS es clave en esta implementación. La función dfs se invoca cuando encontramos la primera letra de la palabra en la matriz. Desde ahí, buscamos de forma recursiva en las cuatro direcciones posibles (arriba, abajo, izquierda, y derecha), verificando que no salgamos de los límites de la matriz y que las letras coincidan nuevamente.

function dfs(matrix, x, y, index) {
  if (index === word.length) return true; // Caso base: si index es igual a la longitud de la palabra
  if (x < 0 || y < 0 || x >= matrix.length || y >= matrix[0].length) return false; // Limitar los bordes del tablero
  if (matrix[x][y] !== word[index]) return false; // Diferencias entre la letra actual y la palabra

  let temp = matrix[x][y]; // Guardamos la letra actual
  matrix[x][y] = '#'; // Marcamos la coordenada como visitada con un simbolo que representa un carácter no existente

  let found = dfs(matrix, x + 1, y, index + 1) || 
              dfs(matrix, x - 1, y, index + 1) ||
              dfs(matrix, x, y + 1, index + 1) ||
              dfs(matrix, x, y - 1, index + 1);

  matrix[x][y] = temp; // Revertimos la marca cuando retrocedemos en el recorrido
  return found;
}

¿Qué consideraciones debemos tomar al diseñar esta solución?

• Manejo de bordes: Al avanzar en la matriz, es esencial asegurarnos de no salirnos de los límites definidos, ya que podría causar errores. Esto se hace verificando las coordenadas antes de avanzar.

• Evitación de revisitas: Para evitar contar el mismo camino dos veces, cambiamos temporalmente el valor de la celda en la matriz a un carácter no existente y lo restauramos después de explorar.

• Optimización de espacio: En lugar de usar una estructura externa para marcar las visitas (como un hash set), reemplazamos temporalmente los valores en la misma matriz, reduciendo así el uso de memoria extra.

Este tipo de enfoque no solo mejora la eficiencia de la búsqueda al centrarse únicamente en rutas plausibles sino que también proporciona flexibilidad para resolver problemas más complejos en el futuro. Te animo a compartir tus experiencias en la sección de comentarios, donde puedes discutir posibles optimizaciones o variaciones, y así continuar aprendiendo y perfeccionando tus habilidades de programación.