题解 | #正则表达式匹配#

class Solution {
public:
    /*
        把能确定的都确定下来,(能确定的一般都是只能满足一种迭代方程的,或者不再迭代方程定义域内的)
    */
    bool match(string str, string pat) {
        int n = str.size(), m = pat.size();
        vector<vector<bool>> dp(n+1,vector<bool>(m+1,false));
        dp[0][0] = true;
        
        for(int j = 2; j <= m; j++){
            // 当 str 为空串时,只能是0次
            if(pat[j-1] == '*') dp[0][j] = dp[0][j-2];
        }
        
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(pat[j-1] == '.' || pat[j-1] == str[i-1]){
                    dp[i][j] =  dp[i-1][j-1];
                }else if(j >= 2 && pat[j-1] == '*'){
                    if(pat[j-2] == '.' || str[i-1] == pat[j-2]){
                        // 能进行匹配可有 0 次 1 次 或 多次!
                        dp[i][j] = dp[i][j-2] || dp[i-1][j-2] || dp[i-1][j];
                    }else {
                        // 不匹配,只能是 0 次!
                        dp[i][j] = dp[i][j-2];
                    }
                }
            }
        }
        return dp[n][m];
    }
};