leetcode 79. Word Search DFS 单词搜索 + 深度优先遍历

墨蓝 2022-06-08 02:13 240阅读 0赞

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,  
Given board =

\[  
\[‘A’,’B’,’C’,’E’\],  
\[‘S’,’F’,’C’,’S’\],  
\[‘A’,’D’,’E’,’E’\]  
\]  
word = “ABCCED”, -> returns true,  
word = “SEE”, -> returns true,  
word = “ABCB”, -> returns false.

题意很简单，就是在一个矩阵中遍历所有可能的字符串，典型的DFS深度深度优先遍历解决。

这是一个很基本的DFS，这种题必须要掌握。

不过本题有个地方需要注意，**设置一个全局的flag变量对DFS做剪枝，否者会超时。**

代码如下：

/*
     * DFS：深度优先遍历
     * 这个是最基本的深度优先遍历，你这傻蛋
     * 
     * Ok ，分析一下DFS在树中的应用， 优先向深处遍历，这个也适用于图，
     * 不过上述都是在一个出发点确定好的情况下，然后做得的遍历，这个出发点可能多个
     * 所以没确定一个出发点，直接做DFS即可，详情分析见下：
     * 
     * */
    public class Solution
    {
        
        //最后结果的全局变量，为什么不用返回值呢？下面有分析
        boolean finalRes=false;
    
        public boolean exist(char[][] board, String word) 
        {
            if(word==null || word.length()<=0 ||board==null || board.length<=0 || board[0].length<=0)
                return false;
    
            //由于我们是从word的第一个字符开始DFS遍历匹配，所以矩阵board中可能不止一个元素，
            //所以要遍历所有可能的word第一个元素word[0]，然后做DFS
            for(int i=0;i<board.length;i++)
            {
                for(int j=0;j<board[0].length;j++)
                {
                    //每当找到一个word[0]，就开始做DFS遍历
                    if(board[i][j]==word.charAt(0))
                    {
                        //设置标记数组，这个是必须的，在DFS算法中必须有一个flag数组
                        boolean [][] visited=new boolean[board.length][board[0].length];
                        visited[i][j]=true;
                        DFS(board,visited,word,1,i,j);
                        //假如找到一个结果就直接返回，
                        if(finalRes==true)
                            return true;            
                        //恢复原状态，但是因为visited数组的作用于就在这个if之中，所以这一句不写也可以
                        visited[i][j]=false;
                    }
                }
            }       
            return false;
        }
    
        private void DFS(char[][] board, boolean[][] visited, String word, int index,int x,int y)
        {
            if(index==word.length())
            {
                finalRes=true;
                return ;
            }
            else
            {
                //&& finalRes==false 这个条件必须添加，否者就会超时，我分析可能是因为一条路找到解，
                //然后就会影响到其他的解，毕竟我们使用的是全局变量，添加这个变量也起到剪枝的效果
                if(x-1>=0 && visited[x-1][y]==false 
                        && board[x-1][y]==word.charAt(index) && finalRes==false)
                {
                    visited[x-1][y]=true;
                    DFS(board, visited, word, index+1, x-1, y);
                    visited[x-1][y]=false;
                }
    
                if(x+1<board.length && visited[x+1][y]==false 
                        && board[x+1][y]==word.charAt(index) && finalRes==false)
                {
                    visited[x+1][y]=true;
                    DFS(board, visited, word, index+1, x+1, y);
                    visited[x+1][y]=false;
                }
    
                if(y-1>=0 && visited[x][y-1]==false
                        && board[x][y-1]==word.charAt(index) && finalRes==false)
                {
                    visited[x][y-1]=true;
                    DFS(board, visited, word, index+1, x, y-1);
                    visited[x][y-1]=false;
                }
    
                if(y+1<board[0].length && visited[x][y+1]==false 
                        && board[x][y+1]==word.charAt(index) && finalRes==false)
                {
                    visited[x][y+1]=true;
                    DFS(board, visited, word, index+1, x, y+1);
                    visited[x][y+1]=false;
                }
    
            }
    
        }
    
    }

下面是C++的做法，就是做一个DFS深度优先遍历

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    
    using namespace std;
    
    
    
    
    class Solution 
    {
    public:
        bool exist(vector<vector<char>>& b, string word) 
        {
            int row = b.size(), col = b[0].size();
            for (int i = 0; i < row; i++)
            {
                for (int j = 0; j < col; j++)
                {
                    vector<vector<bool>> visit(row, vector<bool>(col, false));
                    bool res = dfs(b,visit, i, j, word, 0);
                    if (res == true)
                        return true;
                }
            }
            return false;
        }
    
        bool dfs(vector<vector<char>>& b, vector<vector<bool>>& visit, int x, int y,
            string s, int index)
        {
            int row = b.size(), col = b[0].size();
            if (index == s.length())
                return true;
            else if (x < 0 || x >= row || y < 0 || y >= col || visit[x][y] == true || s[index]!=b[x][y])
                return false;
            else
            {
                visit[x][y] = true;
                bool aa = dfs(b, visit, x - 1, y, s, index + 1);
                bool bb = dfs(b, visit, x + 1, y, s, index + 1);
                bool cc = dfs(b, visit, x, y - 1, s, index + 1);
                bool dd = dfs(b, visit, x, y + 1, s, index + 1);
    
                if (aa || bb || cc || dd)
                    return true;
                else
                {
                    visit[x][y] = false;
                    return false;
                }
            }
        }
    };