2023-8-25
8-25
数组
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
深度优先搜索
// 主函数，判断是否存在符合条件的单词
function exist(board: string[][], word: string): boolean {
// 将单词拆分为字符数组，方便逐个处理
const words: string[] = word.split('');
// 遍历整个二维字符数组
for (let i = 0; i < board.length; i++) {
for (let j = 0; j < board[0].length; j++) {
// 调用深度优先搜索函数，判断从当前位置出发是否能找到目标单词
if (dfs(board, words, i, j, 0)) {
return true; // 如果找到，返回 true
}
}
}
return false; // 如果遍历完整个数组都没有找到，返回 false
}
// 深度优先搜索函数，用于搜索从当前位置出发是否能找到目标单词
function dfs(board: string[][], word: string[], i: number, j: number, k: number): boolean {
// 判断越界和字符不匹配的情况，直接返回 false
if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] !== word[k]) {
return false;
}
// 如果已经匹配到了目标单词的最后一个字符，返回 true
if (k === word.length - 1) {
return true;
}
// 记录当前位置的字符，然后将其置为特殊字符 '\0'
const originalChar = board[i][j];
board[i][j] = '\0';
// 递归搜索当前位置的上、下、左、右四个方向
const res = dfs(board, word, i + 1, j, k + 1) ||
dfs(board, word, i - 1, j, k + 1) ||
dfs(board, word, i, j + 1, k + 1) ||
dfs(board, word, i, j - 1, k + 1);
// 恢复当前位置的字符
board[i][j] = originalChar;
return res; // 返回搜索结果
}
这道题目想了很久，最开始考虑到暴力遍历，没有想到使用深度优先搜索，题解中的剪枝也就是一失败就停止执行