Only 6 lines C++ code!! use Recursion. Clear with detailed explanation.


  • 0
    A

    say "aabc" matches "a* bc", if * stand for 0 a(s), then match "aabc" with "bc"; if * stand for one or more a(s), then consume one a, and keep matching the rest string with pattern, "abc" -> "a* bc".

    the whole process works like this
    "->" means "matchs"
    ":" means "only if"
    "|" means "or"

    "aabcd" -> "a * bcd"

    aabcd -> a * bcd : aabcd -> bcd | abcd->a * bcd; //aabcd->bcd : false;
    abcd->a * bcd: abcd->bcd | bcd -> a * bcd; //abcd->bcd: false;
    bcd->a * bcd: bcd -> bcd;
    bcd->bcd: cd->cd;
    cd->cd:d->d;
    d->d:true;

    bool isMatch(string s, string p) {
        if(s.size()==0 && p.size()==0) return true;
        if(p.size()>1&&p[1]=='*'){
            if(isMatch(s,p.substr(2))) return true;
            if(p[0]=='.'||s[0]==p[0]) return (s.size()>0 && isMatch(s.substr(1),p));
        }else if(p[0]=='.'||s[0]==p[0]) return (s.size()>0 && isMatch(s.substr(1),p.substr(1)));
        return false;
    }

Log in to reply
 

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