个人主页:元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客
个人专栏
力扣递归算法题
http://t.csdnimg.cn/yUl2I
【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;
}
};