【Daily Interview】- 05 单词搜索

题目：

分析

从题目可知，这是类似于一个走迷宫的问题，我们可以套用回溯算法的公式。

关于回溯算法，感兴趣的同学可以看看这篇文章：

回溯算法解题套路框架

那么对于这道题，具体的思路应该是什么呢？

首先肯定是宏观框架的大致逻辑（设查找函数为 exist，二维网格为 board，目标单词为 word）:

• 首先是边界条件：
  • board.length == 0 则返回 false
  • word.length == 0 则返回 true
• 然后我们能找到行和列：
  • row = board.length
  • col = borad[0].length
• 接下来通过一个双重循环，就能找到这个二维网格中的任一字符，而对于每一个当前被遍历到的字符，我们可以进行查找工作

大致代码如下：

const exist = (board, word) => {
  if(board.length === 0) return false
  if(word.length === 0) return true
  const row = board.length
  const col = board[0].length
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      /* find code */
    }
  }
}

那么问题来了，应该如何进行查找呢？

我们将 borad 铺开，就像一个四四方方的迷宫一样：

显然，我们的小球能够往上下左右四个方向进行查找，而边界则是最外面的栅格。

那么我们可以首先确定边界条件：

• i >= row || i < 0
• j >= col || j < 0

上面两种情况说明触边，直接返回 false 即可。

接下来我们通过 board[i][j] 取得小球的值，判断它与 word 的关系，这个时候，我们发现，word 是一串字符串，需要一个 idx 来判断当前需要比较的是其中的第几个字符，而这个 idx，显然就是查找的深度，这里用 cur 表示，那么我们又可以确定边界条件：

• board[i][j] != word[cur] 说明没找到，返回 false 即可
• cur == word.length - 1 说明已经找到了最后一层，并且前面没退出说明 board[i][j] == word[cur] 则返回 true，表示找到了 word 这个单词

接下来就是回溯的模板：

• 保存状态
• 查找
• 回溯状态

这个没什么好说的，我们来看看代码就清楚了：

const exist = (board, word) => {
  if (board.length === 0) return false
  if (word.length === 0) return true
  const row = board.length
  const col = board[0].length
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      const ret = find(i, j, 0)
      if (ret) return true
    }
  }

  function find(i, j, cur) {
    if (i >= row || i < 0) return false
    if (j >= col || j < 0) return false
    const letter = board[i][j]
    if (letter !== word[cur]) return fasle
    if (cur === word.length - 1) return true
    board[i][j] = null
    find(i + 1, j, cur + 1) ||
      find(i - 1, j, cur + 1) ||
      find(i, j + 1, cur + 1) ||
      find(i, j - 1, cur + 1)
    board[i][j] = letter
    return ret
  }
}

结果如下!