Easy Understanding Recursive Back Search, C++


  • 0
    C
    class Solution {
    public:
        bool isMatch(string s, string p) {
            input_string = s;
            match_string = p;
            return is_match(s.length()-1, p.length()-1);
        }
        
        bool is_match(int i, int j) {
            // i,j both finised, matching return true
            if (i==-1 && j==-1) return true;
            // i remains, but j finished, then false
            if (i!=-1 && j==-1) return false;
            // i finished, but j remians, check if j is *.
            if (i==-1 && j!=-1){
                // if i is 0, when j is *, then directly use * as 0
                if (match_string[j]=='*'){
                    return is_match(i,j-2);
                }else{
                    return false;
                }
            }
            if (input_string[i]==match_string[j] || match_string[j]=='.'){
                return is_match(i-1,j-1);
            }else{
                if (match_string[j]=='*'){
                    // if j is * and j -1 match i. use * or not use *
                    if (match_string[j-1] == input_string[i] || match_string[j-1] == '.'){
                        //     not use *          use * again
                        return is_match(i,j-2)  || is_match(i-1,j);
                    }else{
                        // if j is * and j-1 not matching i, not use *
                        return is_match(i,j-2);
                    }
                }else{
                    // if not * and not matching then, return false
                    return false;
                }
            }
        }
        
        string input_string, match_string;
    };
    

    Key point is, in each iteration whenever uses *, it can use it 0 times or multiple times.
    When use 0 times, directly jump 2 characters in the matching string

    is_match(i,j-2)
    

    When uses multiple times (include 1 time), stay at current position

    is_match(i-1, j)
    

Log in to reply
 

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