10. Regular Expression Matching

Given an input string s and a pattern p, implement regular expression matching with support for ‘.’ and ‘*’ where:

• ‘.’ Matches any single character.​​​​
• ‘*’ Matches zero or more of the preceding element.

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

class Solution {
    int dp[21][31];
    bool dfs(string & s, string & p, int sp, int pp) {
        if(dp[sp][pp] != -1) return dp[sp][pp];
        if(sp == s.length()) {
            //if remaining pattern are set of (a~z)* or .* check next
            if(pp != p.length() - 1 and p[pp + 1] == '*') return dp[sp][pp] = dfs(s, p, sp, pp+2);
            return dp[sp][pp] = 0;
        }
        if(pp == p.length() - 1) {
            //matching last pattern character
            if(s[sp] == p[pp] || p[pp] == '.') return dp[sp][pp] = dfs(s,p,sp + 1, pp + 1);
            return dp[sp][pp] = 0;
        }
        if(p[pp + 1] == '*') {
            //if pattern has wildcard
            dp[sp][pp] = dfs(s,p,sp,pp+2);
            if(p[pp] == '.') {
                for(int i = sp; i < s.length(); i++)
                    dp[sp][pp] |= dfs(s,p,i+1,pp+2);
            } else {
                dp[sp][pp] = dfs(s,p,sp,pp+2);
                for(int i = sp; i < s.length() and s[i] == p[pp]; i++)
                    dp[sp][pp] |= dfs(s,p,i+1,pp+2);
            }
            return dp[sp][pp];
        }
        //if pattern matches only single (.)
        if(p[pp] == '.') return dp[sp][pp] = dfs(s, p, sp + 1, pp + 1);;
        
        //mating equal character
        if(s[sp] != p[pp]) return dp[sp][pp] = 0;
        return dp[sp][pp] = dfs(s,p,sp + 1, pp + 1);
    }
public:
    bool isMatch(string s, string p) {
        memset(dp,-1,sizeof(dp));
        for(int i = 0; i < s.length(); i++) dp[i][p.length()] = 0;
        dp[s.length()][p.length()] = 1;
        dfs(s, p, 0, 0);
        return dp[0][0];
    }
};