题目描述:
给定一个 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
仅由大小写英文字母组成
进阶:你可以使用搜索剪枝的技术来优化解决方案,使其在 board
更大的情况下可以更快解决问题?
通过次数
462.9K
提交次数
997.8K
通过率
46.4%
思路和题解:
回溯和剪枝,设置一个函数check(i,j,k)判断从网格的下标[i][j]位置出发,能不能搜索到单词word[k]...word[wordSize-1](即word中下标k开始的后缀字符串)。判断所有的check(i,j,0),只要有一个为真即为真,否则为假。
对于check函数,如果board[i][j]!=word[k],return false;如果board[i][j]!=word[k]&&k==wordSize-1,return true;否则就判断相邻的四个位置能不能搜到word[k+1]...word[wordSize-1]。文章来源:https://www.toymoban.com/news/detail-734407.html
要注意的是,check函数中包含了多次递归调用,如果是c++的话,参数写成传引用,这样比值传递运行速度快,能过。值传递的话我试过过不了。文章来源地址https://www.toymoban.com/news/detail-734407.html
i代码:
class Solution {
public:
//往右,左,下,上四个方向走时行下标的变化和列下标的变化
int directions[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
bool check(vector<vector<char>> &board,int m,int n,vector<vector<int>> &visited,int i,int j,string word,int wordSize,int k)
{
if(board[i][j]!=word[k])
return false;
else if(k==wordSize-1)
return true;
visited[i][j]=1;
for(int direc=0;direc<4;direc++)
{//依次往四个方向走
int newi=i+directions[direc][0],newj=j+directions[direc][1];
if(newi>=0&&newi<m&&newj>=0&&newj<n&&visited[newi][newj]==0)
{
bool flag=check(board,m,n,visited,newi,newj,word,wordSize,k+1);
if(flag)
{
return true;
}
}
}
visited[i][j]=0;
return false;
}
bool exist(vector<vector<char>>& board, string word) {
int m=board.size();
int n=board[0].size();
vector<vector<int>> visited(m,vector<int>(n,0));
int wordSize=word.size();
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
bool flag=check(board,m,n,visited,i,j,word,wordSize,0);
if(flag)
return true;
}
}
return false;
}
};
到了这里,关于力扣每日一题79:单词搜索的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!