<79> Word Search

Description

Question: 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.

Leetcode link: 79. Word Search

Quick Sum-up:

• Input: a 2D array and a string
• Output: a boolean value indicating whether the string can be assembled by the characters in the array

---

Idea

For each cell in the array, if the character is the same as the first character of the string, check whether its neighbors contain the following character. Use a 2D array to record whether a cell has been visited. The recursive loop stops when the end of string is reached. => Pass, 76ms

---

Test cases

Input1	Input2	Expected Output
board=[ ["A","B","C","E"], ["S","F","C","S"], ["A","D","E","E"] ]	word="ABCCED" word="SEE" word="ABCB"	true true false
board=[]	word=""	false
board=[[""]]	word=""	false
board=[[]]	word="ABC"	false
board=[["A"]]	word="ABC"	fasle

---

Solution

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
    let height = board.length
    if (height == 0 || word.length == 0)
        return false
    
    let width = board[0].length
    let record = []
    for (let j = 0; j < height; j++) {
        let row = []
        for (let i = 0; i < width; i++)
            row.push(false)
        
        record.push(row)
    }
    
    let search = function(x, y, index) {
        if (x < 0 || x >= width || y < 0 || y >= height ||
            record[y][x] || board[y][x] != word[index])
            return false
        
        if (index == word.length - 1)
            return true
        
        record[y][x] = true
        
        if (search(x + 1, y, index + 1) ||
           search(x - 1, y , index + 1) ||
           search(x, y + 1, index + 1) ||
           search(x, y - 1, index + 1))
            return true
        
        record[y][x] = false
        
        return false
    }
    
    for (let j = 0; j < height; j++) {
        for (let i = 0; i < width; i++) {
            if (board[j][i] == word[0] && search(i, j, 0))
                return true
        }
    }
        
    return false
};