文章目录

点击这里访问站长的博客

题目

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

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

示例:

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

以下两个题目都是相同的:

• 链接:https://leetcode-cn.com/problems/word-search
• 链接:https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/

题解

var found;
var exist = function (board, searchWord) {
  const candidateStart = [];
  found = false;
  /* 先从迷宫中找到所有可能的出发点 */
  board.map((row, i) => {
    row.map((e, j) => {
      if (e === searchWord[0]) {
        candidateStart.push([i, j]);
      }
    });
  });

  /* 循环从每一个出发点开始寻路 */
  candidateStart.map((start) => search(start, board, searchWord, 1));

  return found;
};

var search = (start, board, searchWord, wordIndex) => {
  /* 每次进入这个函数，那就预示着当前坐标单词已经匹配 */
  if (found) return false;

  let [x, y] = start;

  /* 暂时保存这个位置原来的数据 */
  const tmp = board[x][y];
  /* 标记这个位置已访问过。 */
  board[x][y] = "+";

  const searchChar = searchWord[wordIndex];

  /* 如果已经处理到最后一个单词 */
  if (wordIndex === searchWord.length) {
    found = true;
  }
  if (x > 0 && board[x - 1][y] === searchChar)
    if (search([x - 1, y], board, searchWord, wordIndex + 1))
      // 上
      return true;
  if (x < board.length - 1 && board[x + 1][y] === searchChar)
    if (search([x + 1, y], board, searchWord, wordIndex + 1))
      //下
      return true;
  if (y > 0 && board[x][y - 1] === searchChar)
    if (search([x, y - 1], board, searchWord, wordIndex + 1))
      //左
      return true;
  if (y < board[0].length - 1 && board[x][y + 1] === searchChar)
    if (search([x, y + 1], board, searchWord, wordIndex + 1))
      // 右
      return true;

  /* 将当前位置原来的数据给恢复回来, 如果不这样, 多次回溯的board将会相互影响 */
  board[x][y] = tmp;

  return false;
};