RegularExpressionMatching.cpp

// 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 {
public:
    bool isMatch(string s, string p) {
         int m = s.length(), n = p.length();
        if(n>0 && p[0]=='*') 
            return false;
        vector<vector<bool>> dp(m+1,vector<bool>(n+1,false));
        dp[0][0] = true;
        for(int i=1; i<=n; i++) 
            if(p[i-1] == '*' && dp[0][i-2] == true) 
                dp[0][i] = true;
        for(int i=1; i<=m; i++) 
            dp[i][0] = false;
        for(int i=1; i<=m; i++) {
            for(int j=1; j<=n; j++) {
                if(p[j-1] == s[i-1] || p[j-1] == '.') {
                    dp[i][j] = dp[i-1][j-1];
                }
                else if(p[j-1] == '*') {
                    if(p[j-2] == s[i-1] || p[j-2] == '.') 
                        dp[i][j] = dp[i][j-2] || dp[i-1][j];
                    else 
                        dp[i][j] = dp[i][j-2];
                } 
            }
        }
        return dp[m][n];
    }
};