Easy to understand recursive C++ solution


#1
bool wordsearch(vector<string> &A, string &word, int i, int j, int n){
    
    // if i, j is out of the matrix return false
    if(i < 0 || j < 0 || i >= A.size() || j >= A[0].size())
        return false;
    
    // check if current character is the letter you want, if not return false
    if(A[i][j] == word[n]){
        
        // if complete word is found 
        if(n == word.size()-1)
            return true;
        else{
            // check right left up down for next letter
            bool r = wordsearch(A, word, i, j+1, n+1);
            bool l = wordsearch(A, word, i, j-1, n+1);
            bool u = wordsearch(A, word, i-1, j, n+1);
            bool d = wordsearch(A, word, i+1, j, n+1);
            return (r || l || u || d);
        }
    }
    else
        return false;
    
}


int Solution::exist(vector<string> &A, string word) {
    
    bool wsearch = false;
    for(int i = 0; i < A.size(); i++){
        for(int j = 0; j < A[0].size(); j++){
            
            // check if there is first letter of the word to be found
            if(A[i][j] == word[0]){
                
                // search rest of the letters using recursion
                wsearch = wsearch || wordsearch(A, word, i, j, 0);
            }
        }
    }
    return (wsearch)?1:0;
}

#2

What do you think is the complexity?