export function wordSearch(grid: string[][], word: string): boolean {
let flatGrid = grid.flat();
for( let letter of word) {
const gridLetterIdx = flatGrid.indexOf(letter);
if ( gridLetterIdx === -1) return false;
flatGrid = flatGrid.splice(gridLetterIdx);
}
return true;
}Que solucion tan brillante. Creo que en mi caso me emocione pense mas en otros casos y termine haciendo recursividad.
@alberth de hecho alberth estás en lo correcto, porque algo que fernando no tuvo en cuenta es una parte clave del enunciado, que dice: "La palabra puede construirse a partir de letras en celdas adyacentes de forma secuencial, donde 'adyacentes' significa horizontal o verticalmente vecinas. La misma celda no puede usarse más de una vez en una misma ruta".
Es decir, que si estamos posicionados en un punto, solo podemos ver arriba, abajo, izquierda o derecha. El primer error al aplanar el array (.flat()) es que se destruye la matriz 2D y se pierde la noción de geometría; el algoritmo asume que las letras están conectadas aunque estén en esquinas totalmente opuestas de la sopa de letras.
Pero el error verdaderamente fatal de la lógica ocurre con el uso de .splice() y cómo se comporta ante el índice 0. Para demostrarlo de forma definitiva, supongamos que corremos su código buscando la palabra "AAB" en este tablero:
const tablero = [ ["A", "X"], ["X", "B"] ];
Aplanado queda: ["A", "X", "X", "B"]
Como todos podemos ver, es imposible formar "AAB" porque las letras están en diagonal (no son adyacentes) y además solo hay una "A" en todo el tablero. Sin embargo, miremos los logs de lo que hace su algoritmo paso a paso en la consola:
Buscamos la primera "A":
flatGrid.indexOf("A") devuelve 0. (Imprime 0)
Se ejecuta flatGrid = flatGrid.splice(0);. En JavaScript, .splice(0) extrae absolutamente todo desde el índice 0 hasta el final del array y lo devuelve. Al reasignarlo, flatGrid vuelve a recibir el array completo: ["A", "X", "X", "B"]. (Imprime el array idéntico).
Buscamos la segunda "A":
El bucle pasa a la siguiente letra de la palabra (que es la otra "A"). Como el array quedó exactamente igual en el paso anterior, flatGrid.indexOf("A") vuelve a dar 0.
El algoritmo termina agarrando y reutilizando la misma primerísima "A" del índice 0 que ya había usado antes, clonando mágicamente la celda y violando la regla de que no se puede usar la misma celda más de una vez.
Buscamos la "B":
flatGrid.indexOf("B") devuelve 3. (Imprime 3)
Se ejecuta flatGrid = flatGrid.splice(3);, lo que recorta el array y deja solo ["B"]. (Imprime ["B"]).
Como ninguna búsqueda dio -1, la función termina devolviendo true.
Al final, el algoritmo dice que "AAB" existe en una matriz donde la "A" y la "B" están separadas en diagonal y donde solo había una letra "A". Esto demuestra que no se puede resolver de manera lineal con atajos de arrays y exige obligatoriamente un algoritmo de exploración con coordenadas (Backtracking) para validar la adyacencia real y recordar qué celdas físicas ya fueron pisadas.
Recuerda ser amable. Estás comentando la solución de otra persona. Comparte tu perspectiva de forma constructiva y respetuosa.