An easy understanding backtracing solution


  • 0
    S
    // bracking to try every element as the start character
    bool exist(vector<vector<char> > &board, string word) {
        for(int i = 0; i < board.size(); ++i)
            for(int j = 0; j < board.front().size(); ++j)
                if (bt(board, word, 0, i, j)) 
                    return true;
        return false;
    }
    
    bool bt(vector<vector<char> > &board, string word, int pos, int row, int col) {
        if (row < 0 || row >= board.size()
            || col < 0 || col >= board.front().size() 
            || word[pos] != board[row][col])
            return false;
        
        pos++;
        if (pos == word.size()) return true;
        
        char c = board[row][col];
        board[row][col] = '.';
        
        if (bt(board, word, pos, row + 1, col) || // move down side
            bt(board, word, pos, row - 1, col) || // move up side
            bt(board, word, pos, row, col + 1) || // move right side
            bt(board, word, pos, row, col - 1) ) {// move left side
            return true;
        }
        
        board[row][col] = c;
        return false;
    }

  • 0
    This post is deleted!

  • 0
    C

    when there is a True value returned, will the cell value is the board be restored from '.' to the original value?


Log in to reply
 

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