Time Limit Exceeded C++ DFS solution


  • 0
    B
    class Solution {
    public:
        
        bool startsWith(string s, string word){
            
            int len = s.length();
            
            for(int i = 0 ; i< len; i++){
                
                if(s[i] != word[i]){
                    return false;
                }
            }
        
            return true;
            
        }
        
        
        void helper(vector<vector<char> >& board, string s, int x, int y, bool& res,string word, bool** track){
            
            
            if(x < 0 || x >= board.size() || y < 0 || y >= board[0].size() || track[x][y] == true){
                return;
            }
            
            s += board[x][y];
            
            if(!startsWith(s,word)){
                return;
            }
            
            if(s == word){
                res = true;
                return;
            }
            
            
            track[x][y] = true;
            
            
            helper(board,s,x+1,y,res,word,track);
            helper(board,s,x-1,y,res,word,track);
            helper(board,s,x,y+1,res,word,track);
            helper(board,s,x,y-1,res,word,track);
            
            track[x][y] = false;
            
            
            
            
        }
        
        bool exist(vector<vector<char>>& board, string word) {
            
            bool res = false;
            
            bool** track = new bool*[board.size()];
           
            for(int i = 0 ;i < board.size(); i++){
                track[i] = new bool[board[0].size()];
            }
            
             
            for(int i = 0 ; i < board.size(); i++){
                for(int j = 0 ; j < board[0].size(); j++){
                    
                    track[i][j] = false;
                }
            }
            
            
            
            for(int i = 0 ; i < board.size(); i++){
                for(int j = 0; j < board[0].size(); j++){
                    
                    helper(board,"",i,j,res,word,track);
                }
            }
            
            return res;
            
        }
    };

Log in to reply
 

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