Búsqueda de Palabras en Matrices: Solución y Complejidad

Clase 44 de 52 • Curso de Algoritmos Avanzados: Grafos y Árboles

Resumen

¿Cómo resolver el problema de Word Search?

Resolver problemas algorítmicos puede ser tanto un desafío como una oportunidad de demostrar habilidades. En Word Search, se nos presenta un tablero, es decir, una matriz MxN, compuesta por caracteres y una palabra específica. Nuestro objetivo es verificar si la palabra puede formarse mediante caracteres secuencialmente adyacentes en el tablero. Profundicemos en cómo abordar este intrigante problema.

¿Cuál es la mecánica del problema?

En esencia, este problema nos pide comprobar si podemos "crear" una palabra específica basada en un conjunto de reglas:

La palabra debe formarse con letras adyacentes en el tablero.
Las letras deben ser consecutivas, es decir, la unidad después de otra.
No se puede reutilizar la misma celda para usar nuevamente una letra.

Este desafío es más comúnmente encontrado durante entrevistas de trabajo en empresas tecnológicas grandes, dado que evalúa habilidades de razonamiento lógico y comprensión de algoritmos.

¿Cómo determinar la secuencialidad con un ejemplo?

Para entender mejor, pensemos en un ejemplo:

Supongamos una matriz que tiene las siguientes letras y disposiciones:

  A B C E
  S F C S
  A D E E

Si se nos da la palabra "ABCCED", debemos verificar su existencia considerando las reglas de adyacencia y secuencialidad. Aquí, la solución es verdadera porque la palabra puede formarse de la siguiente manera:
- A se conecta con B (la letra está a la derecha de A).
- B se conecta con C (ahora, la letra está nuevamente a la derecha).
- C se conecta con otra C (pero esta vez bajamos en la columna).
- La segunda C se conecta a E (abajo de nuevo).
- Y finalmente, E se conecta a D (a la derecha).

¿Por qué la misma celda no puede usarse más de una vez?

Esta restricción agrega un desafío mayor, pues nos obliga a ser estratégicos en cómo exploramos el tablero. Puede que encuentre una letra necesaria en una celda, pero luego requiera encontrar esa misma letra en otra ubicación para cumplir con las reglas del juego.

¿Qué se podría considerar como casos raros?

Este aspecto del problema abre la puerta a una variedad de situaciones interesantes, algunas podrían ser:

Tableros donde las letras se repiten muchas veces y pareciera haber múltiples caminos equivalentes.
Palabras que empiezan bien pero no pueden completarse debido a un callejón sin salida.
Matrices pequeñas donde la palabra requiera una navegación tediosa.

¿Cómo abordar la solución?

La clave está en evaluar la complejidad de tiempo y espacio óptimas para abordar el problema. Se recomienda:

Backtracking: Un enfoque muy útil donde se explora de forma recursiva todas las posibilidades de construcción de palabra, retrocediendo solo cuando surge un obstáculo. Es eficiente en término de exploración de posibilidades y se ajusta bien a las restricciones de este problema.
Profundidad y amplitud del algoritmo: Considerar qué tan lejos debemos expandir nuestras posibilidades antes de encontrar la solución correcta.

Podríamos reflexionar sobre estas metodologías para asegurar estrategias efectivas que solventen este problema de forma eficiente. No olvides poner a prueba tu creatividad y considera compartir en la sección de comentarios tus constructos únicos. ¡Buena suerte y sigue explorando y aprendiendo!

Yojan Antonio Pardo Zabala

student•

Esta es mi primera solución para este problema.

package dev.yojanpardo.grafosarboles.backtracking;

import static dev.yojanpardo.Helper.scanner;

public class WordSearch {

    private static final int[][] DIRECTIONS = new int[][] {{1,0},{-1, 0}, {0,1}, {0,-1}};
    public static void main(String[] args) {
        final String[][] matrix = buildMatrix();
        System.out.println("Insert the word you wanna find:");
        String word = scanner.nextLine();

        System.out.printf("Word [%s] is in matrix?: [%b]", word, isWordInMatrix(word, matrix));
    }

    private static boolean isWordInMatrix(String word, String[][] matrix) {

        for(int x = 0; x < matrix.length; x++){
            for(int y = 0; y < matrix[x].length; y++){
                if(word.startsWith(matrix[x][y])){
                    return dfs(word, matrix, x, y, "", x, y).equals(word);
                }
            }
        }
        
        return false;
    }

    private static String dfs(String word, String[][] matrix, int x, int y, String actualWord, int prevX, int prevY) {
        if(word.equals(actualWord)) return actualWord;
        if(x < 0 || x >= matrix.length
                || y < 0 || y >= matrix[x].length
                || actualWord.length() >= word.length()) return "";

        for(int[] direction : DIRECTIONS){
            String newWord = "";
            int newX = x + direction[0], newY = y + direction[1];
            if(!(newX == prevX && newY == prevY))
                newWord = dfs(word, matrix, newX, newY, actualWord + matrix[x][y], x, y);
            if (newWord.equals(word)){
                return word;
            }
        }

        return "";
    }

    private static String[][] buildMatrix() {
        return new String[][] {
                {"H","O","P","N"},
                {"W","L","H","Z"},
                {"Q","A","Y","L"},
                {"T","S","P","X"},
        };
    }
}