79. 单词搜索

1. 题目描述

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false

提示：

• board 和 word 中只包含大写和小写英文字母。
• 1 <= board.length <= 200
• 1 <= board[i].length <= 200
• 1 <= word.length <= 10^3

  2. 解题思路

  这道题目就是使用深度优先遍历+回溯完成。其实现思路就是，向四周进行搜索，只要搜索到一个正确的解，就返回true。需要注意已经遍历过的值就不能遍历了，所以我们把他设置为了0，避免重复遍历。

我们设置了一个flag标记，只要遍历成功一次，就设flag为true，之后就不需要再遍历了。

3. 代码实现

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
    let flag = false // 做标记
    const row = board.length
    const col = board[0].length
    const dfs = (i, j, k) => {
        // 如果已经找到答案，就不往下继续遍历了
        if(flag) return true  
        // 排除条件越界的情况
        if(i < 0 || i >= row || j < 0 || j >= col) return false
        // 如果单词不相等，就返回false
        if(board[i][j] !== word[k]) return false
        // 如果现在已经是单词的最后一个元素，并且该元素和当前元素相等，则说明搜索成功
        if((k === word.length - 1) && (board[i][j] === word[k])) {
            flag = true
            return true
        }
        // 暂存当前的节点值
        const temp = board[i][j]
        // 将当前的节点值设置为0，避免重复遍历
        board[i][j] = 0
        // 分别向上下左右进行深度优先遍历
        const up = dfs(i, j-1, k+1) 
        const down = dfs(i, j+1, k+1) 
        const left = dfs(i-1, j, k+1) 
        const right = dfs(i+1, j, k+1)
        // 遍历完成后，还原当前值
        board[i][j] = temp
        return up || down || left || right
    }
    // 遍历整个二维数组，对元素进行深度优先遍历
    for(let i = 0; i < row; i++){
        for(let j = 0; j < col; j++){
            if(dfs(i, j, 0)) return true
        }
    }
    return false
};

4. 提交结果