TLE for word search question. I don't know why


  • 0
    S

    class Solution {
    public:

    bool dfs(vector<vector<char> > board,vector<vector<int> > &visited,string word,int depth,int x,int y)
    {
        if(x<0||x>=board.size()||y<0||y>=board[0].size())
            return false;
        if(board[x][y]!=word[depth])
            return false;
        if(visited[x][y]==1)
            return false;
        if(depth==word.length()-1)
            return true;
        visited[x][y]=1;
        if(dfs(board,visited,word,depth+1,x,y+1)) return true;
        if(dfs(board,visited,word,depth+1,x,y-1)) return true;
        if(dfs(board,visited,word,depth+1,x+1,y)) return true;
        if(dfs(board,visited,word,depth+1,x-1,y)) return true;
        visited[x][y]=0;
        return false;
    }
    bool exist(vector<vector<char> >& board, string word) {
        int len = word.length();
        vector<vector<int> > visited(board.size(),vector<int> (board[0].size(),0));
        
        for(int i=0;i<board.size();i++)
        {
            for(int j=0;j<board[0].size();j++)
            { 
                if(board[i][j]==word[0])
                {
                    bool ans = dfs(board,visited,word,0,i,j);
                    if(ans)
                        return ans;
                }
            }
        }
        return false;
    }
    

    };


Log in to reply
 

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