天津建设协会网站,织梦网站调用工具,wordpress做商城,wordpress登录可见菜单前言
记录一下刷题历程 力扣第79题 单词搜索 单词搜索
原题目#xff1a;给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。
单词必须按照字母顺序#xff0c;通过相邻…前言
记录一下刷题历程 力扣第79题 单词搜索 单词搜索
原题目给定一个 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
分析
根据题意并没有好的简单的办法只能使用深度优先搜索一个一个匹配以示例1为例先是字母A发现匹配然后分别向上下左右去找下一个匹配的加入向下搜索发现不匹配那么就回溯到A继续搜索其它方向直到搜索出单词返回true。
代码如下
class Solution {
public:bool exist(vectorvectorchar board, string word) {// 获取棋盘的行数和列数int rows board.size();int cols board[0].size();// 创建一个二维布尔数组用于标记每个位置是否被访问过vectorvectorbool visit(rows, vectorbool(cols, false));// 遍历棋盘的每一个位置作为搜索的起点for (int row 0; row rows; row) {for (int col 0; col cols; col) {// 从当前起点位置开始进行深度优先搜索DFSif (dfs(board, word, row, col, 0, visit)) {// 如果找到了目标单词则返回 truereturn true;}}}// 如果遍历完所有起点位置都没有找到目标单词则返回 falsereturn false;}bool dfs(vectorvectorchar board, string word, int row, int col, int index, vectorvectorbool visit) {// 如果当前索引等于目标单词的长度说明找到了完整的单词if (index word.length()) {return true;}// 如果当前坐标超出棋盘边界或者当前字符不匹配或者当前坐标已经被访问过则返回 falseint rows board.size();int cols board[0].size();if (row rows || row 0 || col cols || col 0 || board[row][col] ! word[index] || visit[row][col]) {return false;}// 标记当前位置已被访问visit[row][col] true;// 递归地探索四个方向上下左右查找是否可以继续匹配目标单词bool res dfs(board, word, row 1, col, index 1, visit) || // 向下dfs(board, word, row - 1, col, index 1, visit) || // 向上dfs(board, word, row, col 1, index 1, visit) || // 向右dfs(board, word, row, col - 1, index 1, visit); // 向左// 回溯时取消当前位置的访问标记visit[row][col] false;// 返回是否找到了目标单词return res;}
};解释注释
1.exist 方法该方法负责在棋盘上查找是否存在目标单词。
首先获取棋盘的行数和列数并创建一个二维布尔数组 visit 用于记录每个位置是否已经被访问过。 遍历棋盘上的每一个位置将其作为 DFS 搜索的起点。 对每个起点调用 dfs 方法进行深度优先搜索如果找到了目标单词则返回 true。 如果遍历完所有位置后都没有找到目标单词则返回 false。
2.dfs 方法这是一个递归函数用于从当前坐标进行深度优先搜索。
当 index 等于目标单词的长度时说明找到了完整的单词返回 true。 如果当前位置超出边界、字符不匹配或已经被访问过则返回 false。 标记当前位置已被访问然后递归探索上下左右四个方向。 递归完成后取消当前位置的访问标记回溯以便其他路径可以访问到该位置。 返回是否找到目标单词。
