### 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}

130、200