LeetCode刷题--- 单词搜索
2023-12-30 10:31:37
个人主页:元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客
个人专栏
力扣递归算法题
【C++】? ??
??????http://t.csdnimg.cn/6AbpV
数据结构与算法
?????http://t.csdnimg.cn/hKh2l
前言:这个专栏主要讲述递归递归、搜索与回溯剪枝算法,所以下面题目主要也是这些算法做的 ?
我讲述题目会把讲解部分分为3个部分:
1、题目解析
2、算法原理思路讲解
3、代码实现
单词搜索
题目链接:单词搜索
题目
给定一个?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)全局变量
string Word;
bool visit[10][16];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { 1, -1, 0, 0 };
- Word(word的值)
- visit(二位数组中的元素是否被用过)
- dx[4](用于计算)
- dy[4](用于计算)
(2)设计递归函数
bool dfs(vector<vector<char>>& board, int row, int col, int pos);
- 参数:row(当前需要进?处理的元素横坐标),col(当前需要进?处理的元素横坐标),pos(当前已经处理的元素个数);
- 返回值:布尔值 ;
- 函数作用:判断当前坐标的元素作为字符串中下标 step 的元素出现时,向四个?向传递,查找是否存在路径结果与字符串相同。
递归过程
- 遍历每个位置,标记当前位置并将当前位置的字?作为?字?进?递归,并且在回溯时撤回标记。
- 在每个递归的状态中,我们维护?个步数 pos,表?当前已经处理了?个字?。
- 若当前位置的字?与字符串中的第 pos?个字?不相等,则返回 false。
- 若当前 pos?的值与字符串?度相等,表?存在?种路径使得 word 成?,返回 true。
- 对当前位置的上下左右四个相邻位置进?递归,若递归结果为 true,则返回 true。
- 若相邻的四个位置的递归结果都为 false,则返回 false。
特别地,如果使?将当前遍历到的字符赋值为空格,并在回溯时恢复为原来的字?的?法,则在递归时不会重复遍历当前元素,可达到不使?标记数组的?的。
代码实现
class Solution {
public:
string Word;
bool visit[10][16];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { 1, -1, 0, 0 };
bool dfs(vector<vector<char>>& board, int row, int col, int pos)
{
if (pos == Word.size())
{
return true;
}
int m = board.size();
int n = board[0].size();
for (int i = 0 ; i < 4; i++)
{
int x = row + dx[i], y = col + dy[i];
if (x >= 0 && x < m && y >= 0 && y < n && !visit[x][y] && board[x][y]== Word[pos])
{
visit[x][y] = true;
if (dfs(board, x, y,pos + 1))
return true;
visit[x][y] = false;
}
}
return false;
}
bool exist(vector<vector<char>>& board, string word)
{
Word = word;
for (int i = 0; i < board.size(); i++)
{
for (int j = 0; j < board[i].size(); j++)
{
if (board[i][j] == word[0])
{
visit[i][j] = true;
if (dfs(board, i, j, 1) == true)
return true;
visit[i][j] = false;;
}
}
}
return false;
}
};
文章来源:https://blog.csdn.net/weixin_74268082/article/details/135302046
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!