[C++] why is my solution time exceed? Can somebody find the problem?


  • 0
    W
    bool isfind(int row, int col, int pos, const vector<vector<char>>& board,
                const string& word,vector<vector<bool>> &trace){
        //dir:the direction into this cell, up:1,down:-1;left:-2,right:2,none:0
        if(pos == word.size()) return true;
        if(row < 0 || col < 0 || row >= board.size() || col >= board[0].size()) return false;
        if(board[row][col] != word[pos]) return false;
        
        bool result = false;
        trace[row][col] = true;
        
        if(row - 1 >= 0 && trace[row-1][col] == false )
            result = result || isfind(row-1, col, pos+1,board,word,trace); //up
        if(row + 1 < board.size() && trace[row+1][col] == false )
            result = result || isfind(row+1, col, pos+1,board,word,trace);  //down
        if(col - 1 >= 0 && trace[row][col-1] == false )
            result = result || isfind(row, col-1, pos+1,board,word,trace); //left
        if(col + 1 < board[0].size() && trace[row][col+1] == false )
            result = result || isfind(row, col+1, pos+1,board,word,trace); //right
            
        if(!result) trace[row][col] = false;
    
        return result;
    }
    bool exist(vector<vector<char>>& board, string word) {
        if(word.empty()) return true;
        vector<vector<bool> > trace(board.size(), vector<bool>(board[0].size(),false));
        for(int row = 0; row < board.size(); ++row)
            for(int col = 0; col < board[0].size();++col)
                if(board[row][col] == word[0] && isfind(row,col,0,board,word,trace))
                    return true;
        return false;
    }

  • 0
    T

    A few things. 1: You don't need to create a new trace vector, you can modify the original board to mark visited spot and change it back later. I suspect your original code did not work since creating a new trace vector takes awhile? 2. You don't have to check for " if(row - 1 >= 0 && trace[row-1][col] == false )", since you have already done so in the beginning in "if(row < 0 || col < 0 || row >= board.size() || col >= board[0].size()) return false;" 3. In my version I repeated the if(!result) 4 times. You can try to come up with a better way to do that.

    class Solution {
    public:
        bool isfind(int row, int col, int pos, vector<vector<char>>& board,
                    string& word){
            //dir:the direction into this cell, up:1,down:-1;left:-2,right:2,none:0
            if(pos == word.size()) return true;
            if(row < 0 || col < 0 || row >= board.size() || col >= board[0].size()) return false;
            if(board[row][col] != word[pos]) return false;
        
            bool result = false;
            board[row][col] = ' ';
            if(!result)
                result = isfind(row-1, col, pos+1,board,word); //up
            if(!result)
                result = isfind(row+1, col, pos+1,board,word);  //down
            if(!result)
                result = isfind(row, col-1, pos+1,board,word); //left
            if(!result)
                result = isfind(row, col+1, pos+1,board,word); //right
            board[row][col] = word[pos];
    
            return result;
        }
        bool exist(vector<vector<char>>& board, string word) {
            if(word.empty()) return true;
            
            for(int row = 0; row < board.size(); ++row)
                for(int col = 0; col < board[0].size();++col)
                    if(board[row][col] == word[0] && isfind(row,col,0,board,word))
                        return true;
            return false;
        }
    };

Log in to reply
 

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