Regular Expression Matching (Leetcode 10)

主要是讨论等于 '*' 的情况。设dp[i][j] 为以 i-1 结尾的 s，和以 j-1 结尾的 p 是否match。通项公式为：

dp[i][j] = dp[i-1][j-1]   =>  if s[i-1] == p[j-1] or p[j-1] == '.'
if p[j-1] == '*':
        dp[i][j] = dp[i][j-2];  // '*' 匹配 0 的情况
        or dp[i][j] = (s[i-1] == p[j-2] or p[j-2] == '.') and dp[i-1][j] // '*' 匹配不为 0 的情况

class Solution {
public:
    bool isMatch(string s, string p) {
        int lenA = s.length(), lenB = p.length();

        vector<vector<bool>> dp(lenA+1, vector<bool>(lenB+1, false));
        dp[0][0] = true;
        for(int i=1; i<=lenB; i++){
            if(p[i-1] == '*' && i > 1) dp[0][i] = dp[0][i-2];
        }
        
        for(int i=1; i<=lenA; i++){
            dp[i][0] = false;
            for(int j=1; j<=lenB; j++){
                if(p[j-1] == '*'){
                    if(j == 1) continue;
                    dp[i][j] = dp[i][j-2] || ((s[i-1] == p[j-2] || p[j-2] == '.') && dp[i-1][j]);
                }
                else if(p[j-1] == '.' || s[i-1] == p[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = false;
                }
            }
        }
        return dp[lenA][lenB];
    }
};

若需要节约空间，用滚动数组：

class Solution {
public:
    bool isMatch(string s, string p) {
        int lenA = s.length(), lenB = p.length();

        vector<vector<bool>> dp(2, vector<bool>(lenB+1, false));
        dp[0][0] = true;
        for(int i=1; i<=lenB; i++){
            if(p[i-1] == '*' && i > 1) dp[0][i] = dp[0][i-2];
        }
        
        for(int i=1; i<=lenA; i++){
            dp[i%2][0] = false;
            for(int j=1; j<=lenB; j++){
                if(p[j-1] == '*'){
                    if(j == 1) continue;
                    dp[i%2][j] = dp[i%2][j-2] || ((s[i-1] == p[j-2] || p[j-2] == '.') && dp[(i-1)%2][j]);
                }
                else if(p[j-1] == '.' || s[i-1] == p[j-1]){
                    dp[i%2][j] = dp[(i-1)%2][j-1];
                }else{
                    dp[i%2][j] = false;
                }
            }
        }
        return dp[lenA%2][lenB];
    }
};