单词搜索问题（涉及递归等）

目录

一·题目：

二·思路解释：

三·解答代码：

---

一·题目：

newcode题目链接： 单词搜索_牛客题霸_牛客网

二·思路解释：

思路：个人理解是找到word中的第一个元素，然后去递归的上下左右查找，最后根据word的下标变化等看是否返回true

下面具体说一下个人思路（也是根据大佬悟出来的）：这里有点明显想考的是递归的使用，这里为了方便记录遍历到原数组位置

以及防止查找时候查到已经找到的原数组中元素（word中有连续重复元素在board中出现）等，因此不方便在原数组里面操作，因此重新建一个二维数组（这里个人称作真假表->主要记录遍历原数组找到元素位置，给它在真假表中用true标记，而默认是false，这里标记它的路径也能防止“走重的操作了”）.

因此这里首先建立一个递归函数，首先要想完成这个操作需要哪些参数等呢？ word和它的索引 ，board和它的下标i，j，以及我们的真假表（这里下标直接用board的i，j即可）；

一开始先遍历原数组找到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(vector<string>& board,int i,int j, string word,int word_index,vector<vector<bool>>TF_graph){
        if(word_index==word.size()) return true;
         if(i<0||i>=board.size()||j<0||j>=board[0].size()||TF_graph[i][j]==true||board[i][j]!=word[word_index]) return false;
         
         TF_graph[i][j]=true;
         bool target_on=recursion_find(board,i-1,j,word,word_index+1,TF_graph);
         bool target_under=recursion_find(board,i+1,j,word,word_index+1,TF_graph);
         bool target_left=recursion_find(board,i,j-1,word,word_index+1,TF_graph);
         bool target_right=recursion_find(board,i,j+1,word,word_index+1,TF_graph);
         // TF_graph[i][j]=false;
         return  target_on||target_under||target_left|| target_right;
            

     }
    bool exist(vector<string>& board, string word) {
         int m=board.size();
         int n=board[0].size();
         vector<vector<bool>>TF_graph(m,vector<bool>(n,false));
         for(int i=0;i<m;i++){
            for(int j=0;j<n;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;

    }
};

                     ​​​​​​​       若有补充希望大佬们留言.        

原文地址：https://blog.csdn.net/2401_82648291/article/details/142533292

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！