How to analyse the time complexity of the backtracking/recursive method?


  • 0
    X

    It seems that this problem is pretty similar to a combination problem with size of m*n letters, given that the grid board is of m rows and n columns. However, it confuses me when it comes to the constraint to search only within either vertical or horizontal neighbours. Could anyone help to explain the analysis of time and space?

    class Solution {
        bool helper(vector<vector<char>>& board, int i, int j,  string word,int length)
        {
            /*** terminating cases ***/
            if (length == word.size()) //found
                return true;
            
            if (i < 0 || j < 0 || i == board.size() || j == board[0].size()) //not found 
                return false;
                
            if (board[i][j] == '*' || board[i][j] != word[length])
                return false;
            
            /*** board[i][j] matches word[length], recursive search ***/
            char tmp = board[i][j];
            board[i][j] = '*';
            bool result = helper(board, i-1, j, word, length+1) 
                        || helper(board, i+1, j, word, length+1)
                        || helper(board, i, j+1, word, length+1)
                        || helper(board, i, j-1, word, length+1);
            board[i][j] = tmp;
            
            return result;
        }
    public:
        bool exist(vector<vector<char>>& board, string word) {
            int m = board.size(), n = board[0].size();
            for (int i = 0; i < m; i++)
                for (int j = 0; j < n; j++)
                {
                    if (helper(board, i, j, word, 0)) 
                        return true;
                }
                
            return false;
            
        }
    };

Log in to reply
 

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