79.Word Search

Given an m x n board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where "adjacent" cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

Constraints:

• m === board.length
• n === board[i].length
• 1 <= m, n <= 200
• 1 <= word.length <= 103
• board and word consists only of lowercase and uppercase English letters.

y列
x行   C  A  A
      A  A  A
      B  C  D

AAB -> true

y列
x行   a  a  a  a
      a  a  a  a
      a  a  a  a

Analyze

y列
x行   A  B  C  E   word: ABCB
      S  F  C  S
      A  D  E  E

二维数组找路径适合用回溯法。每个节点根据下、右、上、左四个方向回溯查找元素。

拿 ABCCED 作为例子, 括号中为淘汰的值。

A(S) -> B(F) -> C -> C -> E(空、E、C) -> D

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
  for (let x = 0; x < board.length; x++) {
    for (let y = 0; y < board[x].length; y++) {
      if (word.length === 1 && word[0] === board[x][y]) {
        return true
      }
      if (word[0] === board[x][y]) {
        const ifValid = backTrace(board, word, 1, x, y, [])
        if (ifValid) return ifValid
      }
    }
  }
  return false
};

/**
 * start: means start of word
 * x: row
 * y: column
* */
var backTrace = (board, word, start, x, y, used) => {
  used.push(`${x},${y}`)
  const useBottom = used.indexOf(`${x + 1},${y}`) === -1 && word[start] === (board[x + 1] && board[x + 1][y])
  const useRight = used.indexOf(`${x},${y + 1}`) === -1 && word[start] === (board[x] && board[x][y + 1])
  const useTop = used.indexOf(`${x - 1},${y}`) === -1 && word[start] === (board[x - 1] && board[x - 1][y])
  const useLeft = used.indexOf(`${x},${y - 1}`) === -1 && word[start] === (board[x] && board[x][y - 1])
  if (start === word.length - 1 && (useRight || useBottom || useLeft || useTop)) {
    return true
  }

  if (useBottom) {
    const tag = backTrace(board, word, start + 1, x + 1, y, used)
    used.pop()
    if (tag) return tag
  }
  if (useRight) {
    const tag = backTrace(board, word, start + 1, x, y + 1, used)
    used.pop()
    if (tag) return tag
  }
  if (useTop) {
    const tag = backTrace(board, word, start + 1, x - 1, y, used)
    used.pop()
    if (tag) return tag
  }
  if (useLeft) {
    const tag = backTrace(board, word, start + 1, x, y - 1, used)
    used.pop()
    if (tag) return tag
  }
  return false
}

思考: 这道题的解法可以用来解决生活中部分「迷宫类」的问题。

优化

• 几个关键点
  • 终止条件优化
  • 使用 for 循环优化 4 个方向

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
  for (let x = 0; x < board.length; x++) {
    for (let y = 0; y < board[x].length; y++) {
      const ifValid = backTrace(board, word, 0, x, y, [])
      if (ifValid) return true
    }
  }
  return false
};

var directions = [[1, 0], [0, 1], [-1, 0], [0, -1]] // 下、右、上、左

/**
 * start: means start of word
 * x: row
 * y: column
* */
var backTrace = (board, word, start, x, y, used) => {
  const key = `${x},${y}`
  if (start === word.length - 1 && used.indexOf(key) === -1 && word[start] === (board[x] && board[x][y])) {
    return true
  }

  for (let i = 0; i < directions.length; i++) {
    if (word[start] === (board[x] && board[x][y]) && used.indexOf(key) === -1) {
      used.push(key)
      const tag = backTrace(board, word, start + 1, x + directions[i][0], y + directions[i][1], used)
      used.pop()
      if (tag) return true
    }
  }

  return false
}

优化后代码量减少 32%。

sister title

130、200