79.单词搜索

79.单词搜索

Category	Difficulty	Likes	Dislikes
algorithms	Medium (46.40%)	1400	-

Tags
Companies
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED” 输出：true
示例 2：

输入：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “SEE” 输出：true
示例 3：

输入：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCB” 输出：false

提示：

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board 和 word 仅由大小写英文字母组成

进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

---

Discussion | Solution

思路

暴力回溯，回溯结束点判断最终结果是否等于单词即可，其中可以将不属于单词的字母设为-1，进行剪枝

解答

/*
 * @lc app=leetcode.cn id=79 lang=javascript
 *
 * [79] 单词搜索
 */

// @lc code=start
/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
  const dfs = (i, j, str) => {
    const char = board[i] && board[i][j];

    if (
      i < 0 ||
      i > board.length - 1 ||
      j < 0 ||
      j > board[i].length - 1 ||
      char === -1 ||
      str.length === word.length
    )
      return str === word;

    const firstIndex = word.indexOf(char);

    if (firstIndex === -1) {
      board[i][j] = -1;
      return false;
    }

    const origin = board[i][j];

    board[i][j] = -1;

    const res =
      dfs(i + 1, j, str + char) ||
      dfs(i - 1, j, str + char) ||
      dfs(i, j + 1, str + char) ||
      dfs(i, j - 1, str + char);

    board[i][j] = origin;

    return res;
  };

  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[i].length; j++) {
      if (board[i][j] === word[0] && dfs(i, j, "")) return true;
    }
  }

  return false;
};
// @lc code=end