leetcode 79 Word Search (using JavaScript)

Question

I tried to solve leetcode 79 using JavaScript, but this test case fails:

[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]] "ABCB"

My code is as follows:

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
    let row = board.length, col = board[0].length;
    
    let dfs = (word, r, c) =>{
        if (!word.length){
            return true;
        }
        else if (r>=0 && r<row && c>=0 && c<col && word[0] === board[r][c]){

            let tmp = board[r][c];
            board[r][c] = '#';
            console.log(word[0], board, r,c)
            if (dfs(word.substr(1), r+1, c) || dfs(word.substr(1), r-1, c) || dfs(word.substr(1), r, c+1) || word.substr(1), r, c-1){
                return true;
            }
            board[r][c] = tmp;
            return false;
        }
        else{
            return false;
        }
    }
    for (let r=0; r<row; r++){
        for (let c=0; c<col; c++){
            if (dfs(word, r, c)){
                return true;
            }
        }
    }
    return false;
};

My Python solution used the same logic, and it passed. I really don't where I did wrong and have been stucked for hours....

Emma Marcier · Accepted Answer · 2020-10-25 22:55:35Z

So far so good!

My guess is that the bug would be in the Depth First Search else if and else.
This'd pass, similarly with a DFS:

const directions = [
    [-1, 0],
    [0, 1],
    [1, 0],
    [0, -1]
];

const exist = (board, word) => {
    if (board.length === 0) {
        return false;
    }

    const depthFirstSearch = (row, col, k) => {
        if (board[row][col] !== word[k]) {
            return false;
        }

        if (k === word.length - 1) {
            return true;
        }

        board[row][col] = 'VISITED';
        for (const [diffRow, diffCol] of directions) {
            const nextRow = row + diffRow;
            const nextCol = col + diffCol;
            if (
                nextRow > -1 &&
                nextCol >= 0 &&
                nextRow < board.length &&
                nextCol < board[0].length
            ) {
                if (depthFirstSearch(nextRow, nextCol, k + 1)) {
                    return true;
                }
            }
        }

        board[row][col] = word[k];
        return false;
    };

    for (let row = 0; row < board.length; ++row) {
        for (let col = 0; col < board[0].length; ++col) {
            if (depthFirstSearch(row, col, 0)) {
                return true;
            }
        }
    }

    return false;
};

Collectives™ on Stack Overflow

leetcode 79 Word Search (using JavaScript)

1 Answer 1

So far so good!

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

So far so good!

Comments

Your Answer

Sign up or log in

Post as a guest

Related