Question

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

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: string[][],
    visited: boolean[][],
    r: number,
    c: number,
    word: string,
    index: number
): boolean {
    if (index === word.length) {
        return true;
    }

    const rows: number = grid.length;
    const cols: number = 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: boolean =
        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: string[][], word: string): boolean {
    const rows: number = grid.length;
    const cols: number = grid[0].length;

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

    for (let r: number = 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(): void {
    const grid: string[][] = [
        ['a', 'b', 'c', 'e'],
        ['s', 'f', 'c', 's'],
        ['a', 'd', 'e', 'e']
    ];

    const word = "see";

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

main();



/*
run:

1

*/

 

70+ SQL courses for beginners and professionals