10 Regular Expression Matching

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

my own solution!

class Solution {
public:
    bool isMatch(string s, string p) {
        int ns = s.size(), np = p.size();
        int is = ns-1, ip = np-1;
        stack<int> back_p, back_s;
        while ( is >= 0 ) {
            if ( ip >= 0 and ( s[is] == p[ip] or p[ip] == '.' ) ) {
                is -= 1; ip -= 1;
                continue;
            }
            if ( ip >= 0 and p[ip] == '*' ) {
                while ( p[ip] == '*' ) ip--;
                back_p.push(ip);
                back_s.push(is);
                ip -= 1;
                continue;
            }
            if ( back_p.empty() ) return false;
            while ( ! back_p.empty() ) {
                ip = back_p.top(); back_p.pop();
                is = back_s.top(); back_s.pop();
                if ( s[is] == p[ip] or p[ip] == '.' ) {
                    back_p.push(ip--);
                    back_s.push(--is);
                    break;
                }
                else continue;
            }
        }
        if ( ip == -1 ) return true;
        if ( ip == 0 and p[ip] != '*' ) return false;
        while ( ip >= 0 ) {
            if ( p[ip] != '*' and p[ip+1] != '*' ) return false;
            ip -= 1;
        }
        return true;
    }
};

Notes: The overall thoughts are similar to "wildcard matching". But we have to pay attention to the the different usage of '*'. Since the occurence of '*' have backwards impact. So we decide to compare from the end of the string/pattern.

• Matching case: simply continue
• special case of '*'
  • tracing to the first non-'*' character. push the current is and ip to the stack;
  • first consider the case that '*' represents zero proceeding element. ip -= 1 and continue;
• Something goes wrong case:
  • take the top element from stack back_s and back_p (the first position to go back.)

    is = back_s.top(); back_s.pop();
    ip = back_p.top(); back_p.pop();
    

    • If those two doesn't match, keep taking the next position to go back.
    • If those two matches, push back the new positions to go back:

      back_p.push(ip--); // position in p does not change
      back_s.push(--is); // position in s minus 1.
      

Recursive solution

class Solution {
public:
    bool help(string s, int is, string p, int ip) {
        int ns = s.size(), np = p.size();
        if ( ip == np ) return ( is == ns );
        if ( ip == np-1 or p[ip+1] != '*') {
            return ((p[ip] == s[is] or ( p[ip] == '.' and is <= ns-1 )) and help(s, is+1, p, ip+1) );
        }
        while ( p[ip] == s[is] or (p[ip] == '.' and is <= ns-1) ) {
            if (help(s, is, p, ip+2)) return true;
            is += 1;
            if ( is == ns ) break;
        }
        return help(s, is, p, ip+2);
    }
    bool isMatch(string s, string p) {
        return help(s, 0, p, 0);
    }
};

• If the current position