79. Word Search

Problem

https://leetcode.com/problems/word-search/

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

Solution

Yet another BFS.

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
    if (board.length <= 0 || board[0].length <= 0 || word.length <= 0) {
        return false
    }

    var height = board.length
    var width = board[0].length

    for (let row = 0; row < height; row += 1) {
        for (let col = 0; col < width; col += 1) {
            // start to match the whole word
            if (board[row][col] === word[0]) {
                if (word.length === 1) {
                    return true
                }

                let path = 1
                board[row][col] = false
                if (wordFinder(row, col, board, word, path)) {
                    return true
                }
                board[row][col] = word[--path]
            }
        }
    }

    // row, col, word index
    function wordFinder(row, col, board, word, path) {
        const directions = [
            -1, 0,
            0, 1,
            1, 0,
            0, -1
        ]

        for (let d = 0; d < 2*4;) {
            let r = row + directions[d++]
            let c = col + directions[d++]
            if (r >= 0 && c >= 0 && r < height && c < width
                    && board[r][c] === word[path]) {
                if (++path === word.length) {
                    return true
                }
                board[r][c] = false
                if (wordFinder(r, c, board, word, path)) {
                    return true
                }
                board[r][c] = word[--path]

            }
        }
        return false
    }

    return false
};

stack way

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
    if (board.length <= 0 || board[0].length <= 0 || word.length <= 0) {
        return false
    }

    const height = board.length
    const width = board[0].length
    const directions = [
        [-1, 0],
        [0, 1],
        [1, 0],
        [0, -1]
    ]

    const stack = []

    for (let row = 0; row < height; row += 1) {
        for (let col = 0; col < width; col += 1) {
            if (board[row][col] === word[0]) {

                board[row][col] = false
                stack.push({
                    row: row,
                    col: col,
                    w: 0,
                    direction: -1
                })

                while (stack.length > 0) {
                    let data = stack[stack.length-1]

                    if (data.w + 1 === word.length) {
                        return true
                    }

                    let row = data.row
                    let col = data.col
                    let dir = data.direction
                    let w = data.w

                    if (dir >= 3) {
                        stack.pop()
                        board[row][col] = word[data.w]
                    } else {
                        w += 1
                        dir += 1
                        data.direction = dir
                        let r = row + directions[dir][0]
                        let c = col + directions[dir][1]
                        if (r >= 0 && c >= 0
                                && r < height && c < width
                                && w < word.length
                                && board[r][c] === word[w]) {
                            board[r][c] = false
                            stack.push({
                                row: r,
                                col: c,
                                w: w,
                                direction: -1
                            })
                        }
                    }
                }
            }
        }
    }
    return false
};