力扣79单词搜索

力扣79单词搜索

题目详情

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

输入输出样例

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

解法：回溯算法

       bool exist(vector<vector<char>>&board,string word)
        {
    
            int rLength=board.size();
            int cLength=board[0].size();

            //建立二维数组,用来表示位置是否被访问过，数组大小与board的大小需要一致
            vector<vector<int>>visitesd(rLength,vector<int>(cLength)); 

            for(int i=0;i<rLength;i++)
            {
    
                for(int j=0;j<cLength;j++)
                {
    
                    //判断是否属于单词搜索
                    if(check(board,visitesd,i,j,word,0))
                    {
    
                        return true;
                    }
                }
            }
            return false;
         }

         //k指代当前是word的第几个字符
         bool check(vector<vector<char>>&board,vector<vector<int>>&visited,int i,int j,string word,int k)
         {
    
            if(board[i][j]!=word[k])
            {
    
                return false;
            }
            else if(k==word.size()-1)
            {
    
                return true;
            }

            //当word[k]在board中存在，但并未到字符串末尾时
            //1.首先将标志位设置为true
            visited[i][j]=true;

            //建立方向数组，标记可以移动的方向
            vector<pair<int,int>>direction{
    {
    0,1},{
    0,-1},{
    1,0},{
    -1,0}};

            //标记周围是否存在相同的字符串
            bool res=false;
            for(auto dir:direction)
            {
    
                //newi,newj 代表新的坐标值
                int newi=i+dir.first;
                int newj=j+dir.second;
                //判断newi和newj是否超出边界或则不存在
                if(newi>=0&&newi<board.size()&&newj>=0&&newj<board[0].size())
                {
    
                    //当该值并没有被访问过
                    if(!visited[newi][newj])
                    {
    
                        //从里到外的循环
                        bool flag=check(board,visited,newi,newj,word,k+1);
                        if(flag)
                        {
    
                            //当下一个字符存在的时候便跳出循环
                            res=true;
                            break;
                        }
                    }
                }

            }
            //重置标记位
            visited[i][j]=false;
            return res;

         }