79. Word Search

LeetCode - The World's Leading Online Programming Learning PlatformLeetCode

time: O(n x m x w)

space: O(n x m)

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */

let visited;
var exist = function(board, word) {
    
    visited = new Array(board.length);
    for (let i = 0; i < board.length; i++) {
        visited[i] = new Array(board[0].length).fill(0);
    }

    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            const flag = search(board, word, i, j, 0);
            if (flag) return true;
        }
    }

    return false;
};

function search(board, word, row, col, idx = 0) {
    if (idx >= word.length) {
        return true;
    }

    if (row < 0 || row > board.length - 1) {
        return false;
    }
    if (col < 0 || col > board[0].length - 1) {
        return false;
    }

    if (visited[row][col] === 1) return false;

    if (word.charAt(idx) !== board[row][col]) {
        return false;
    }

    visited[row][col] = 1;

    const up = search(board, word, row + 1, col, idx + 1);
    const down = search(board, word, row - 1, col, idx + 1);
    const left = search(board, word, row, col - 1, idx + 1);
    const right = search(board, word, row, col + 1, idx + 1);

    visited[row][col] = 0;

    return up || down || left || right;
}