北京 网站建设咨询顾问公司,网络公司有几家,建站优化系统,用阿里云做网站注意事项目录
一题目#xff1a;
二思路解释#xff1a;
三解答代码#xff1a; 一题目#xff1a; newcode题目链接#xff1a; 单词搜索_牛客题霸_牛客网
二思路解释#xff1a; 思路#xff1a;个人理解是找到word中的第一个元素#xff0c;然后去递归的上下左右查找
二·思路解释
三·解答代码 一·题目 newcode题目链接 单词搜索_牛客题霸_牛客网
二·思路解释 思路个人理解是找到word中的第一个元素然后去递归的上下左右查找最后根据word的下标变化等看是否返回true
下面具体说一下个人思路也是根据大佬悟出来的这里有点明显想考的是递归的使用这里为了方便记录遍历到原数组位置
以及防止查找时候查到已经找到的原数组中元素word中有连续重复元素在board中出现等因此不方便在原数组里面操作因此重新建一个二维数组这里个人称作真假表-主要记录遍历原数组找到元素位置给它在真假表中用true标记而默认是false这里标记它的路径也能防止“走重的操作了”.
因此这里首先建立一个递归函数首先要想完成这个操作需要哪些参数等呢 word和它的索引 board和它的下标ij以及我们的真假表这里下标直接用board的ij即可 一开始先遍历原数组找到word首元素的位置从它开始进行递归当然这里有种特殊情况下面会讲到 1·首先不是递归嘛然后先找递归终止条件这里可以根据遍历上下左右的时候出现的越界问题总结了四个返回false的情况根据后面的查找操作也不难找出另两个即可能出现查找了曾经找的元素不是word中对应下标所指向的元素。--这里就得到了递归不成立的六大终止条件。 如果我们根据实例1试到最后一次对归还会发现最后一次如果再次遍历它应该设置一个返回真的条件 于是就得到了另一个返回真的条件---也就是当word索引越界的情况 2·也就是如何递归这里如果上面没有被返回也就是到了下面也就是找到了因此可以在真假表对应映射位置填入true然后接着往它左右递归即可最后呢根据递归完往回溯可以看出这里最后返回的上下左右的bool类型值应该是或的关系。 3·这里可以考虑给真假表对应的当时填入true位置复原成false当然这里对本题解无关系 这里有一个细节问题也就是上面说的这里找到对应word[0]我们就返回这个递归函数这里是错误的表示掉过坑这里可能是这种情况[CAA,AAA,BCD] AAB--这里如果找到第一个A然后递归下去最后返回的一定是false然而此例子返回的应该是true因此如果它是false就接着遍历board继续找然后再次递归 因此这里如果递归函数返回false不一定题解真实false但是如果返回true则题解一定是true。因此注意好这个基本到这就没什么问题了。 下面画图以实例1为例子解释如何递归的 三·解答代码 class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param board string字符串vector * param word string字符串 * return bool布尔型*/bool recursion_find(vectorstring board,int i,int j, string word,int word_index,vectorvectorboolTF_graph){if(word_indexword.size()) return true;if(i0||iboard.size()||j0||jboard[0].size()||TF_graph[i][j]true||board[i][j]!word[word_index]) return false;TF_graph[i][j]true;bool target_onrecursion_find(board,i-1,j,word,word_index1,TF_graph);bool target_underrecursion_find(board,i1,j,word,word_index1,TF_graph);bool target_leftrecursion_find(board,i,j-1,word,word_index1,TF_graph);bool target_rightrecursion_find(board,i,j1,word,word_index1,TF_graph);// TF_graph[i][j]false;return target_on||target_under||target_left|| target_right;}bool exist(vectorstring board, string word) {int mboard.size();int nboard[0].size();vectorvectorboolTF_graph(m,vectorbool(n,false));for(int i0;im;i){for(int j0;jn;j){if(board[i][j]word[0]){//return recursion_find(board,i,j,word,0,TF_graph);if (recursion_find(board,i,j,word,0,TF_graph)) {return true;}}}}return false;}
}; 若有补充希望大佬们留言.
