Question

How to search for a word in a grid of characters with JavaScript

Answer 1

// Use a depth‑first search (DFS) from every cell that matches the first letter,
// exploring all valid directions until the full word is matched.

function dfs(grid, visited, r, c, word, index) {
    if (index === word.length) {
        return true;
    }

    const rows = grid.length;
    const cols = grid[0].length;

    if (r < 0 || c < 0 || r >= rows || c >= cols) {
        return false;
    }

    if (visited[r][c]) {
        return false;
    }

    if (grid[r][c] !== word[index]) {
        return false;
    }

    visited[r][c] = true;

    const found =
        dfs(grid, visited, r + 1, c, word, index + 1) ||
        dfs(grid, visited, r - 1, c, word, index + 1) ||
        dfs(grid, visited, r, c + 1, word, index + 1) ||
        dfs(grid, visited, r, c - 1, word, index + 1);

    visited[r][c] = false;
    return found;
}

function wordExist(grid, word) {
    const rows = grid.length;
    const cols = grid[0].length;

    const visited = Array.from({ length: rows }, () =>
        Array(cols).fill(false)
    );

    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (dfs(grid, visited, r, c, word, 0)) {
                return true;
            }
        }
    }

    return false;
}

function main() {
    const grid = [
        ['a', 'b', 'c', 'e'],
        ['s', 'f', 'c', 's'],
        ['a', 'd', 'e', 'e']
    ];

    const word = "see";

    const result = wordExist(grid, word);
    console.log(result ? 1 : 0);
}

main();



/*
run:

1

*/

 

70+ SQL courses for beginners and professionals