剑指 Offer 19. 正则表达式匹配

原题链接：剑指 Offer 19. 正则表达式匹配

 

solution:

状态表示:dp[i][j]表示s的前i个字符能否和p的前j个字符匹配
转移方程:

        如果s[i] == p[j]表示s的第i个字符和p的第j个字符相同,因此dp[i][j] = dp[i - 1][j - 1].
        当p[j] == '.'的时候,由于'.'可以表示任何字符所以dp[i][j] = dp[i - 1][j - 1].
        当 p(j) == '*' 时，若 j>=2，dp[i][j] 可以从dp[i][j - 2]  转移，表示丢弃这一次的 '*' 和它之前的那个字符；若 i>0 且 s[i] == p[j - 1]，表示这个字符可以利用这个 '*'，则可以从dp[i - 1][j] 转移，表示利用 '*'。

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(),n = p.size();
        s = " " + s;
        p = " " + p;
        //dp[i][j]表示s的前i个字符和p的前j个字符能否匹配
        vector<vector<bool>> dp(m + 1, vector<bool> (n + 1, false));
        dp[0][0] = true;

        for(int i = 0;i <= m;i++)
            for(int j = 1;j <= n;j++) {
                if(i > 0 && (s[i] == p[j] | p[j] == '.'))
                    dp[i][j] = dp[i][j] | dp[i - 1][j - 1];
                if(p[j] == '*') {
                    if(j >= 2) {
                        dp[i][j] = dp[i][j] | dp[i][j - 2];
                    if (i > 0 && (s[i] == p[j - 1] || p[j - 1] == '.'))
                        dp[i][j] = dp[i][j] | dp[i - 1][j];
                    }
                }
            }
        return dp[m][n];
    }
};