给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

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

思路

  1. 常规的深度优先搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
var exist = function (board, word) {
  const [M, N] = [board.length, board[0].length]
  const search = (i, j, subWord, marked) => {
    if (i < 0 || i >= M || j < 0 || j >= N) {
      return false
    }
    const markedKey = `${i},${j}`
    if (marked[markedKey]) {
      return false
    }
    if (board[i][j] !== subWord[0]) {
      return false
    }
    marked = {
      ...marked,
      [markedKey]: true,
    }
    subWord = subWord.substring(1)
    if (!subWord) {
      return true
    }
    return (
      search(i + 1, j, subWord, marked) ||
      search(i, j + 1, subWord, marked) ||
      search(i - 1, j, subWord, marked) ||
      search(i, j - 1, subWord, marked)
    )
  }
  for (let i = 0; i < M; ++i) {
    for (let j = 0; j < N; ++j) {
      if (search(i, j, word, {})) {
        return true
      }
    }
  }
  return false
}

但面对下面用例执行时间超时

1
2
3
4
5
6
7
8
9
10
11
exist(
  [
    ['A', 'A', 'A', 'A', 'A', 'A'],
    ['A', 'A', 'A', 'A', 'A', 'A'],
    ['A', 'A', 'A', 'A', 'A', 'A'],
    ['A', 'A', 'A', 'A', 'A', 'A'],
    ['A', 'A', 'A', 'A', 'A', 'A'],
    ['A', 'A', 'A', 'A', 'A', 'A'],
  ],
  'AAAAAAAAAAAAAAa'
)

进入递归前，初步判断矩阵字符与目标字符串的匹配程度

1
2
3
4
5
6
7
8
9
10
11
12
13
// ……
  let matchCount = 0
  for (let i = 0; i < M; ++i) {
    for (let j = 0; j < N; ++j) {
      if (charCounts[board[i][j]] > 0) {
        ++matchCount
        --charCounts[board[i][j]]
      }
    }
  }
  if (matchCount < word.length) {
    return false
  }