leetcode 79. 单词搜索

[xxleyi]

题：

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

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

 

示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

解：此题依旧是回溯，只不过在回溯外面还需要套一层循环。做此题时，遇到超时，迟迟未能解决，后来几番探究，才意识到在某一个地方未及时抽身而退，导致回溯过程中明明已经得到正确答案，却未及时返回。

「回溯」的「循环不变式」不好显式描述：递归枚举，避免重复枚举，避免无效枚举，回退时恢复现场。

• 避免重复枚举 => 有次序的循环或记忆化的字典
• 避免无效枚举 => 充分剪枝 + 及时抽身而退（比较少见，但此题我就是栽在这个上面）
• 回退前恢复现场 => 多来几次，能感受到具体指什么，以及怎么操作

var exist = function(board, word) {
  // helper variable
  const dir = [[0, 1], [-1, 0], [0, -1], [1, 0]]
  const rowNum = board.length
  const colNum = board[0].length
  // helper function
  const validIJ = (i, j) => i >= 0 && i < rowNum && j >= 0 && j < colNum

  // used to record visited path
  let path = {}

  // 回溯：递归 + 回退前清理现场 + 最大程度剪枝
  function backtrack(i = 0, j = 0, m = 0) {
    // 到达终点：可返回答案
    if (m === word.length - 1) {
      return board[i][j] === word[m]
    }

    // 判断是否还能继续
    if (board[i][j] === word[m]) {
      // 能继续时，继续深入
      path[[i, j]] = true
      for (const [di, dj] of dir) {
        let ni = di + i, nj = dj + j
        // 剪枝
        if (validIJ(ni, nj) && !path[[ni, nj]]) {
          // 此题坑到我的点就在这：没意识到这个可以直接返回的点
          // 从而导致明明已经得到了答案，还是那继续回溯，导致最终超时
          const res = backtrack(ni, nj, m + 1)
          // 判断是否可以返回
          if (res) return true
        }
      }
      // 退回前恢复现场
      path[[i, j]] = false
    }

    // 不能继续直接返回 false
    return false
  }

  for (let i = 0; i < rowNum; i++) {
    for (let j = 0; j < colNum; j++) {
      if (backtrack(i, j, 0)) return true
    }
  }
  return false
};