Búsqueda de Palabras en Matrices usando Backtracking y DFS

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

Resumen

¿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.

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.
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:

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.

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!

Daniel Ortiz

student•

No es el mas eficiente pero lo logre en JS

const ADJACENT_MARTIX = [
    [0, 1], [0, -1], //x
    [1, 0], [-1, 0], //y
    [1, 1], [-1, -1], //xy
];

const CAFE_BOARD = [
    ['A', 'C', 'L', 'C'],
    ['F', 'A', 'A', 'I'],
    ['I', 'F', 'E', 'U'],
];

const duplicateBoard = (board) => board.map((row) => row.map((col) => col));

const isAdjactedWord = (board, word, x, y, index) => {
    return ADJACENT_MARTIX.filter((adj) => {
        const adjX = x + adj[0];
        const adjY = y + adj[1];
        if (
            board[adjX] != undefined &&
            board[adjX][adjY] != undefined &&
            board[adjX][adjY] === word[index]
        ) {
            board[adjX][adjY] = '';
            return true;
        }
        return false;
    });
}

console.assert(isAdjactedWord(duplicateBoard(CAFE_BOARD), 'CAFE',0,1,1).length==3, 'Adjacent matrix length')
console.assert(isAdjactedWord(duplicateBoard(CAFE_BOARD), 'CAFE',1,1,2).length==2, 'Adjacent matrix length')
console.assert(isAdjactedWord(duplicateBoard(CAFE_BOARD), 'CAFE',2,1,3).length==1, 'Adjacent matrix length')




const isWord = (board, word, x, y) => {
    let index =1;
    const auxBard = board.map((row) => row.map((col) => col));
    let adjacent = isAdjactedWord(auxBard, word, x, y, 1);
    while (adjacent.length > 0) {
        index++;
        if (index === word.length) return true;
        
        adjacent= adjacent.map((adj) => 
        {
            point = [adj[0]+x, adj[1]+y];
            result =isAdjactedWord(auxBard, word, adj[0]+x, adj[1]+y, index);
            result = result.map((adj) =>{
                return [adj[0]+point[0], adj[1]+point[1]]
            })
            return result;
        });
        adjacent=adjacent.reduce((acc, cur) => {
            if (cur.length > 0) {
                acc.push(...cur)
            }
            return acc
        }, [])
        if (index === word.length) return true;

    };

    return false
}
console.assert(isWord(duplicateBoard(CAFE_BOARD), 'CAFE',0,1)==true, 'Is word inside bard')



function searchWord(board, word) {
    word = word.toUpperCase();
    if (word.length === 0 || board.length == 0) return false;

    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[i].length; j++) {
            if (board[i][j] === word[0] && isWord(board, word, i, j)) {
                return true;
            }
        }
    }
    return false;

}

console.assert(searchWord([], "") === false, 'empty board and word');
console.assert(searchWord(CAFE_BOARD, "CAFE") === true, 'Search Cafe');

Usuario anónimo

user•

Solución inicial en JS

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
	let exist = false;
	let coordinatesForFirsChar = [];
	for (let x = 0; x < board.length; x++) {
		for (let y = 0; y < board[x].length; y++) {
			if (board[x][y] === word.charAt(0)) {
				coordinatesForFirsChar.push({ x, y });
			}
		}
	}

	coordinatesForFirsChar.forEach((pairOfCordinates) => {
		if (findWord(board, word.slice(1, word.length), pairOfCordinates)) {
			exist = true;
		}
	});

	return exist;
};

function findWord(board, word, pairOfCordinates) {
	const { x, y } = pairOfCordinates;

	const m = board.length;
	const n = board[0].length;
	const newWord = word.slice(1, word.length);

	if (x + 1 < m && word.charAt(0) == board[x + 1][y]) {
        if (newWord.length === 0) return true;
        board[x+1][y] = "-1"
		return findWord(board, newWord, {
			x: x + 1,
			y: y
		});
	} else if (x - 1 >= 0 && word.charAt(0) == board[x - 1][y]) {
        if (newWord.length === 0) return true;
        board[x-1][y] = "-1"
		return findWord(board, newWord, {
			x: x - 1,
			y: y
		});
	} else if (y + 1 < n && word.charAt(0) == board[x][y + 1]) {
		if (newWord.length === 0) return true;
        board[x][y+1] = "-1"
		return findWord(board, newWord, {
			x: x,
			y: y + 1
		});
	} else if (y - 1 >= 0 && word.charAt(0) == board[x][y - 1]) {
		if (newWord.length === 0) return true;
        board[x][y-1] = "-1"
		return findWord(board, newWord, {
			x: x,
			y: y - 1
		});
	} else {
		return false;
	}
}

Andres Silva Vega

student•

Mi solución en JS usando recursividad:

class BusquedaPalabras {
    constructor (){
        this.tablero = [
            ["A","B","C","C"],
            ["S","F","C","S"],
            ["A","D","E","E"]
        ];
        this.caminos = [[0,-1],[1,0],[0,1],[-1,0]];
        this.solucion = [];
    }
    buscar(palabra){
        const regex = /^[A-Z]+$/g
        if(regex.exec(palabra) == null){
            console.error("Palabra invalida");
            return;
        }
        this.palabra = palabra;
        for(let y = 0; y < this.tablero.length; y++){
            for(let x = 0; x < this.tablero.length; x++){
                if(this.tablero[y][x] == this.palabra[0]){
                    this.solucion = this.accionBuscar([[x,y]],1);
                    return this.solucion;
                }
            }
        }
        
    }
    accionBuscar(solucion, indexPalabra){
        // caso ultimo
        if(indexPalabra == this.palabra.length){
            return solucion;
        }
        let ultimaSolucion = [];
        for(let c = 0; c < this.caminos.length; c++){
            let nx = this.caminos[c][0] + solucion[solucion.length-1][0];
            let ny = this.caminos[c][1] + solucion[solucion.length-1][1];
            if (nx >= 0 && nx < this.tablero[0].length && ny >= 0 && ny < this.tablero.length && this.tablero[ny][nx] == this.palabra[indexPalabra]){
                ultimaSolucion = this.accionBuscar([...solucion, [nx,ny] ],indexPalabra+1);
                if(typeof ultimaSolucion == "object"){
                    return ultimaSolucion;
                }
            }
        }
        return -1;
    }
    dibujaSolucion(){
        let mostrar = "";
        for(let y = 0; y < this.tablero.length; y++){
            for(let x = 0; x < this.tablero[0].length; x++){
                if(this.solucion.findIndex( e => e[0] == x && e[1] == y) == -1){
                    mostrar += ` ${this.tablero[y][x].toLowerCase()} `;
                } else {
                    mostrar += `|${this.tablero[y][x]}|`;
                }
            }
            mostrar += "\n";
        }
        console.log(`Palabra buscada ${this.palabra}`);
        console.log(mostrar);
    }
}
const o = new BusquedaPalabras;
o.buscar("ABCCED");
o.dibujaSolucion();

Miguel Angel Reyes Moreno

student•

en Python


from typing import List



class Solution:

&#x20;   def exist(self, board: List\[List\[str]], word: str) -> bool:

&#x20;       rows, cols = len(board), len(board\[0])

&#x20;      &#x20;

&#x20;       def backtrack(r, c, index):

&#x20;           if index == len(word):

&#x20;               return True

&#x20;          &#x20;



&#x20;           if r < 0 or r >= rows or c < 0 or c >= cols or board\[r]\[c] != word\[index]:

&#x20;               return False

&#x20;          &#x20;



&#x20;           temp = board\[r]\[c]

&#x20;           board\[r]\[c] = '#'

&#x20;          &#x20;



&#x20;           for dr, dc in \[(0, 1), (1, 0), (0, -1), (-1, 0)]:

&#x20;               if backtrack(r + dr, c + dc, index + 1):

&#x20;                   return True

&#x20;          &#x20;



&#x20;           board\[r]\[c] = temp

&#x20;          &#x20;

&#x20;           return False

&#x20;      &#x20;



&#x20;       for r in range(rows):

&#x20;           for c in range(cols):

&#x20;               if backtrack(r, c, 0):

&#x20;                   return True

&#x20;      &#x20;

&#x20;       return False