Easy C++ solution using DFS and backtracking [AC]


  • 0

    Solution

    We will use depth first search to find the string in the grid and will backtrack when a solution is not found.

    Code

    class Solution {
    private:
        bool DFSHelper(vector<vector<char>>& board, string word, int k, int i, int j, int vis[][1000])
        {
            if(k == word.length())
                return true;
            if(i<0 || j<0)
                return false;
            if(i==board.size() || j== board[0].size())
                return false;
            if(vis[i][j]==1)
                return false;
            
            if(board[i][j]==word[k])
            {
                vis[i][j]=1;
                if(DFSHelper(board, word, k+1, i+1,j,vis))
                        return true;
                if(DFSHelper(board, word, k+1, i,j+1,vis))
                        return true;
                if(DFSHelper(board, word, k+1, i-1,j,vis))
                        return true;
                if(DFSHelper(board, word, k+1, i,j-1,vis))
                        return true;
                vis[i][j]=0;
            }
            return false;
        }
    public:
        bool exist(vector<vector<char>>& board, string word) {
            int vis[1000][1000];
            memset(vis,0,sizeof(vis));
            for(int i=0;i<board.size();i++)
                for(int j=0;j<board[0].size();j++)
                   if(board[i][j] == word[0] )
                    {
                        memset(vis,0,sizeof(vis));
                        if(DFSHelper(board, word, 0, i,j,vis))
                            return true;
                    }
            return false;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.