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

题目描述：

给定一个 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(MN3^L ），M,N 为网格的长度与宽度。L 为字符串 word 的长度。在图上每个点进行一个深度搜先搜索，总共有 MN 个点。搜索失败，最深的搜索的深度为(L-1)，每个点有上下左右四个搜索方向，方式搜索过的点不进行搜索，所以为 3^L。所以总的时间复杂度为 O(MN3^L ）。
② 空间复杂度：

代码实现

代码实现（思路一（深度优先搜索（回溯）））：

class Solution {
private:// backtracking 函数进行深度优先搜索，尝试在board上找到单词wordvoid 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;  // 如果没有找到，回溯}}}// 如果遍历完所有可能的起点都没有找到，返回 falsereturn false;}
};

以思路一为例进行调试

#include<iostream>
#include <vector>
using namespace std;class Solution {
private:// backtracking 函数进行深度优先搜索，尝试在board上找到单词wordvoid 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;  // 如果没有找到，回溯}}}// 如果遍历完所有可能的起点都没有找到，返回 falsereturn 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)原题链接
欢迎大家和我沟通交流(✿◠‿◠)