无锡优化网站价格,定制一款app,图册制作,做淘宝客网站要申请什么LeetCode 热题 100_单词搜索#xff08;60_79#xff09; 题目描述#xff1a;输入输出样例#xff1a;题解#xff1a;解题思路#xff1a;思路一#xff08;深度优先搜索#xff08;回溯#xff09;#xff09;#xff1a; 代码实现代码实现#xff08;思路一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上找到单词wordvoid backtracking(vectorvectorchar board, string word, int row, int col, vectorvectorbool 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(vectorvectorchar board, string word) {// mark 用来标记当前位置是否已经访问过避免重复访问vectorvectorbool mark(board.size(), vectorbool(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;}
};以思路一为例进行调试
#includeiostream
#include vector
using namespace std;class Solution {
private:// backtracking 函数进行深度优先搜索尝试在board上找到单词wordvoid backtracking(vectorvectorchar board, string word, int row, int col, vectorvectorbool 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(vectorvectorchar board, string word) {// mark 用来标记当前位置是否已经访问过避免重复访问vectorvectorbool mark(board.size(), vectorbool(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[])
{// 初始化网格vectorvectorchar board {{A,B,C,E},{S,F,C,S},{A,D,E,E}};// 初始化要查找的单词 wordstring word ABCCED;// 创建 Solution 类的对象 s用于调用 exist 函数// 如果找到了输出 trueSolution s;if (s.exist(board,word)){couttrue;}else{coutfalse;}return 0;
}部分代码解读
初始化二维vector的大小
vectorvectorbool mark(board.size(), vectorbool(board[0].size()));作用是创建一个与 board 尺寸相同的二维布尔数组 mark并初始化为 false。
LeetCode 热题 100_单词搜索60_79)原题链接 欢迎大家和我沟通交流(✿◠‿◠)
