RegularExpression_03.cpp

class Solution {
public:
    bool isMatch(string s, string p) {
        int len_s = s.size(), len_p = p.size();
        bool dp[len_s+1][len_p+1];
        //Since the dp[len_s][len_p] means comparison of two empty string, which should be true.
        dp[len_s][len_p] = true;
        
        for(int i = len_s; i>= 0; i--){
            for(int j = len_p; j>= 0; j--){
                //We already set the value to true above;
                if(i == len_s && j == len_p) continue;
                
                bool firstMatch = (i<len_s && j< len_p && (s[i] == p[j] || p[j] == '.'));
                
                if(j+1 < len_p && p[j+1] == '*'){
                    dp[i][j] = dp[i][j+2]|| (firstMatch&&dp[i+1][j]);
                }
                else
                    dp[i][j] = firstMatch&&dp[i+1][j+1];
            }
        }
        return dp[0][0];
    }
};