LeetCode热题100_单词搜索（60_79_中等_C++）（深度优先搜索（回溯））(初始化二维vector

LeetCode 热题 100_单词搜索（60_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

提示： m == board.length n = board[i].length 1 <= m, n <= 6 1 <= word.length <= 15 board 和 word 仅由大小写英文字母组成

题解： 解题思路： 思路一（深度优先搜索（回溯））：

1、根据搜索的过程，可以容易的推出使用深度优先的方法进行搜素。 具体思路如下： ① 在进行深度优先遍历的时候先判断表格中字母与word中第一个字母是否相同，若相同则进行深度优先搜索，每次搜索依次与word中的字母进行比较。 ② 若每次比较字母相同则将此字母标记为已搜索，继续进行搜索，搜索到所有word中的字母则返回true。 ③ 若不相同则将此次搜索之前搜索过的字母标记为未搜索。并从开始搜索的第一个字母的下一个字母进行判断搜索，直至搜索完整个图。

2、复杂度分析： ① 时间复杂度：一个非常宽松的上界为 O(MN3L ），M,N 为网格的长度与宽度。L 为字符串 word 的长度。在图上每个点进行一个深度搜先搜索，总共有 MN 个点。搜索失败，最深的搜索的深度为(L-1)，每个点有上下左右四个搜索方向，方式搜索过的点不进行搜索，所以为 3L。所以总的时间复杂度为 O(MN3L ）。 ② 空间复杂度：

代码实现 代码实现（思路一（深度优先搜索（回溯）））： class Solution { private: // backtracking 函数进行深度优先搜索，尝试在board上找到单词word void backtracking(vector<vector<char>>& board, string &word, int row, int col, vector<vector<bool>> &mark, int i, bool &flag){ // 递归出口：当已匹配完所有字符时（i == word.size() - 1），说明找到了匹配的单词 if (i == word.size() - 1) { flag = true; // 设置 flag 为 true，表示找到了单词 } // 尝试向上移动 if (row - 1 >= 0 && !mark[row - 1][col] && board[row - 1][col] == word[i + 1]) { mark[row - 1][col] = true; // 标记当前位置为已访问 backtracking(board, word, row - 1, col, mark, i + 1, flag); // 递归继续搜索 if (flag) return; // 如果找到了单词，立即返回 mark[row - 1][col] = false; // 如果未找到，回溯，标记为未访问 } // 尝试向下移动 if (row + 1 < board.size() && !mark[row + 1][col] && board[row + 1][col] == word[i + 1]) { mark[row + 1][col] = true; backtracking(board, word, row + 1, col, mark, i + 1, flag); if (flag) return; mark[row + 1][col] = false; } // 尝试向左移动 if (col - 1 >= 0 && !mark[row][col - 1] && board[row][col - 1] == word[i + 1]) { mark[row][col - 1] = true; backtracking(board, word, row, col - 1, mark, i + 1, flag); if (flag) return; mark[row][col - 1] = false; } // 尝试向右移动 if (col + 1 < board[0].size() && !mark[row][col + 1] && board[row][col + 1] == word[i + 1]) { mark[row][col + 1] = true; backtracking(board, word, row, col + 1, mark, i + 1, flag); if (flag) return; mark[row][col + 1] = false; } } public: // 主函数：遍历棋盘，尝试从每个位置开始查找单词 bool exist(vector<vector<char>>& board, string word) { // mark 用来标记当前位置是否已经访问过，避免重复访问 vector<vector<bool>> mark(board.size(), vector<bool>(board[0].size())); bool flag = false; // 标记是否找到单词 // 遍历棋盘中的每个位置，查找与单词首字母匹配的字符 for (int row = 0; row < board.size(); row++) { for (int col = 0; col < board[0].size(); col++) { // 如果当前位置的字母与单词的第一个字母相同，开始深度优先搜索 if (board[row][col] == word[0]) { mark[row][col] = true; // 标记当前位置已访问 backtracking(board, word, row, col, mark, 0, flag); // 开始递归搜索 if (flag) return true; // 如果找到了，立即返回 mark[row][col] = false; // 如果没有找到，回溯 } } } // 如果遍历完所有可能的起点都没有找到，返回 false return false; } }; 以思路一为例进行调试 #include<iostream> #include <vector> using namespace std; class Solution { private: // backtracking 函数进行深度优先搜索，尝试在board上找到单词word void backtracking(vector<vector<char>>& board, string &word, int row, int col, vector<vector<bool>> &mark, int i, bool &flag){ // 递归出口：当已匹配完所有字符时（i == word.size() - 1），说明找到了匹配的单词 if (i == word.size() - 1) { flag = true; // 设置 flag 为 true，表示找到了单词 } // 尝试向上移动 if (row - 1 >= 0 && !mark[row - 1][col] && board[row - 1][col] == word[i + 1]) { mark[row - 1][col] = true; // 标记当前位置为已访问 backtracking(board, word, row - 1, col, mark, i + 1, flag); // 递归继续搜索 if (flag) return; // 如果找到了单词，立即返回 mark[row - 1][col] = false; // 如果未找到，回溯，标记为未访问 } // 尝试向下移动 if (row + 1 < board.size() && !mark[row + 1][col] && board[row + 1][col] == word[i + 1]) { mark[row + 1][col] = true; backtracking(board, word, row + 1, col, mark, i + 1, flag); if (flag) return; mark[row + 1][col] = false; } // 尝试向左移动 if (col - 1 >= 0 && !mark[row][col - 1] && board[row][col - 1] == word[i + 1]) { mark[row][col - 1] = true; backtracking(board, word, row, col - 1, mark, i + 1, flag); if (flag) return; mark[row][col - 1] = false; } // 尝试向右移动 if (col + 1 < board[0].size() && !mark[row][col + 1] && board[row][col + 1] == word[i + 1]) { mark[row][col + 1] = true; backtracking(board, word, row, col + 1, mark, i + 1, flag); if (flag) return; mark[row][col + 1] = false; } } public: // 主函数：遍历棋盘，尝试从每个位置开始查找单词 bool exist(vector<vector<char>>& board, string word) { // mark 用来标记当前位置是否已经访问过，避免重复访问 vector<vector<bool>> mark(board.size(), vector<bool>(board[0].size())); bool flag = false; // 标记是否找到单词 // 遍历棋盘中的每个位置，查找与单词首字母匹配的字符 for (int row = 0; row < board.size(); row++) { for (int col = 0; col < board[0].size(); col++) { // 如果当前位置的字母与单词的第一个字母相同，开始深度优先搜索 if (board[row][col] == word[0]) { mark[row][col] = true; // 标记当前位置已访问 backtracking(board, word, row, col, mark, 0, flag); // 开始递归搜索 if (flag) return true; // 如果找到了，立即返回 mark[row][col] = false; // 如果没有找到，回溯 } } } // 如果遍历完所有可能的起点都没有找到，返回 false return false; } }; int main(int argc, char const *argv[]) { // 初始化网格 vector<vector<char>> board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}}; // 初始化要查找的单词 'word' string word = "ABCCED"; // 创建 Solution 类的对象 's'，用于调用 'exist' 函数 // 如果找到了，输出 "true" Solution s; if (s.exist(board,word)) { cout<<"true"; }else{ cout<<"false"; } return 0; } 部分代码解读

初始化二维vector的大小

vector<vector<bool>> mark(board.size(), vector<bool>(board[0].size()));

作用是创建一个与 board 尺寸相同的二维布尔数组 mark，并初始化为 false。

LeetCode 热题 100_单词搜索（60_79)原题链接 欢迎大家和我沟通交流(✿◠‿◠)