Dose Time Limit Exceeded mean that I've passed other smaller test cases?


  • 0
    D

    Can anyone help with this? I used DFS but don't know how to speed it up?

    class Solution {
        public:
            bool exist(vector<vector<char> > &board, string word) {
                int row = board.size();
                int col = board.size();
                int len=word.length();
                if (len>row&&len>col) 
                   return false;
                vector<vector<bool> > visited(row, vector<bool>(col,false));
                
                for (int r=0; r<row; r++)
                {
                    for (int c=0; c<col; c++)
                    {
                        if (board[r][c]==word[0])
                        {
                            if (len==1)
                            return true;
                            visited[r][c]=true;
                            if (helper(board,word,r,c, row, col,1, visited))
                              return true;
                            visited.resize(row,vector<bool>(col,false));
                        }
                    }
                }
                
                return false;
            }
            bool valid(int r, int c, int row, int col)
            {
                if (r>=0&&r<row&&c>=0&&c<col)
                   return true;
                else
                   return false;
            }
            
            bool helper(vector<vector<char>> &b, string word, int r, int c, int row, int col, int i, vector<vector<bool>> visited)
            {
                if (i==word.length())
                    return true;
                int rplus=r++, rminus=r--,cplus=c++, cminus=c--;
                
        
                //find neighbors if there are valid ones
                if (valid(rplus,c,row,col)&&visited[rplus][c]==false)
                {
                    if (b[rplus][c]==word[i])
                    {
                       visited[rplus][c]=true;
                       return helper(b,word,rplus,c,row,col, i+1, visited);
                    }
                }
                
                if (valid(rminus,c,row,col)&&visited[rminus][c]==false)
                {
                    if (b[rminus][c]==word[i])
                      {
                          visited[rminus][c]=true;
                          return helper(b,word,rminus,c,row,col,i+1,visited);
                      }
                }
                
                if (valid(r,cplus,row,col)&&visited[r][cplus]==false)
                {
                    if (b[r][cplus]==word[i])
                    {
                        visited[r][cplus]= true;
                       return helper(b,word,r, cplus, row, col, i+1,visited);
                    }
                }
                
                if (valid(r,cminus,row,col)&&visited[r][cminus]==false)
                {
                    if (b[r][cminus]==word[i])
                    {
                        visited[r][cminus]=true;
                       return helper(b,word,r,cminus,row,col,i+1,visited);
                    }
                }
                
                return false;
            }
        };

Log in to reply
 

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