单词搜索
给定一个 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 更大的情况下可以更快解决问题？
解法
遍历的方向有四个，遍历时要注意以下条件
- 每个单元格只能用一次
- path长度不能超过word
- 下一个字符要和word对应
visited数组就用来记录访问过的位置
path按道理来讲也可以用数组来表示，并且进行回溯，但是实际性能不如重复创建string。
ts
function exist(board: string[][], word: string): boolean {
let res = false
const wordlen = word.length
const h = board.length
const w = board[0].length
const visited: boolean[][] = new Array(h).fill(0).map(() => new Array(w).fill(false))
const stackBack = (path: string, i: number, j: number) => {
if(res) return // 如果已经找到答案了，剩下的递归也不用继续了
if(path === word){
res = true
return
}
// 可以朝四个方向移动, 不能超出边界
// 每个单元格只能用一次
// path长度不能超过word
// 下一个字符要和word对应
const len = path.length
if(i - 1 >= 0 && visited[i - 1][j] === false && len + 1 <= wordlen && board[i - 1][j] === word[len]){
visited[i - 1][j] = true
stackBack(path + board[i - 1][j], i - 1, j)
visited[i - 1][j] = false // 回溯访问矩阵
}
if(i + 1 < h && visited[i + 1][j] === false && len + 1 <= wordlen && board[i + 1][j] === word[len]){
visited[i + 1][j] = true
stackBack(path + board[i + 1][j], i + 1, j)
visited[i + 1][j] = false // 回溯访问矩阵
}
if(j - 1 >= 0 && visited[i][j - 1] === false && len + 1 <= wordlen && board[i][j - 1] === word[len]){
visited[i][j - 1] = true
stackBack(path + board[i][j - 1], i, j - 1)
visited[i][j - 1] = false // 回溯访问矩阵
}
if(j + 1 < w && visited[i][j + 1] === false && len + 1 <= wordlen && board[i][j + 1] === word[len]){
visited[i][j + 1] = true
stackBack(path + board[i][j + 1], i, j + 1)
visited[i][j + 1] = false // 回溯访问矩阵
}
}
for (let i = 0; i < h; i++) {
for (let j = 0; j < w; j++) {
// 只有当前单元格等于单词首字母，才开始DFS
if (board[i][j] === word[0]) {
visited[i][j] = true; // 标记起点为已访问
stackBack(board[i][j], i, j)
if (res) return true; // len=1：已经匹配了首字母，匹配下一个
visited[i][j] = false; // 回溯起点标记
}
}
}
return res
};