盐城网站建设有限公司,泰州网站建设定制,淘宝的网站架构,嘉兴公司制作网站的题目描述#xff1a;
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。
单词必须按照字母顺序#xff0c;通过相邻的单元格内的字母构成#xff0c;其中“相邻”单元格…题目描述
给定一个 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.lengthn board[i].length1 m, n 61 word.length 15board 和 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]kwordSize-1return true否则就判断相邻的四个位置能不能搜到word[k1]...word[wordSize-1]。
要注意的是check函数中包含了多次递归调用如果是c的话参数写成传引用这样比值传递运行速度快能过。值传递的话我试过过不了。
i代码
class Solution {
public://往右左下上四个方向走时行下标的变化和列下标的变化int directions[4][2]{{0,1},{0,-1},{1,0},{-1,0}};bool check(vectorvectorchar board,int m,int n,vectorvectorint visited,int i,int j,string word,int wordSize,int k){if(board[i][j]!word[k])return false;else if(kwordSize-1)return true;visited[i][j]1;for(int direc0;direc4;direc){//依次往四个方向走int newiidirections[direc][0],newjjdirections[direc][1];if(newi0newimnewj0newjnvisited[newi][newj]0){bool flagcheck(board,m,n,visited,newi,newj,word,wordSize,k1);if(flag){return true;}}}visited[i][j]0;return false;}bool exist(vectorvectorchar board, string word) {int mboard.size();int nboard[0].size();vectorvectorint visited(m,vectorint(n,0));int wordSizeword.size();for(int i0;im;i){for(int j0;jn;j){bool flagcheck(board,m,n,visited,i,j,word,wordSize,0);if(flag)return true;}}return false;}
};
