【剑指 offer】正则表达式匹配（DP）

1、题目描述

请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（含0次）。
在本题中，匹配是指字符串的所有字符匹配整个模式。

例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配。

样例

输入：
s="aa"
p="a*"
输出:true

2、状态表示：

• f[i][j] 表示p从j开始到结尾，是否能匹配s从i开始到结尾。

3、状态转移：

1.如果p[j + 1]不是*，那么f[i][j]为真，有两种情况s[i] == p[j],且f[i + 1][j + 1]为真。
2.如果p[j + 1]是*，那么满足下列一种情况f[i][j]就为真。

• f[i][j + 2]是真；（相当于*匹配0个）
• s[i]可以和p[j]匹配，且f[i + 1][j]为真。（*匹配一个或者多个）

3.第一种情况很好理解，对于第二中情况的解释：

• 如果*匹配0个，那么f[i][j] = f[i][j + 2].
• 如果匹配1个的话，f[i][j] = f[i + 1][j].这里已经包含了s[i]==p[j],否则如果不等就包含了在 匹配0个里面，不用判断s[i]==p[j].
• 如果匹配2个的话，f[i][j] = f[i + 1][j] = f[i +1 +1][j];
• 如果。。。。可以知道都包含在f[i + 1][j]。中

4、C++代码：

class Solution {
public:
    vector<vector<int>> f;
    string s, p;
    int n, m;
    bool isMatch(string _s, string _p) {
        s = _s, p = _p;
        n = s.size(), m = p.size();
        f = vector<vector<int>>(n + 1, vector<int>(m + 1, -1));//状态记录。
        return dp(0, 0);
    }
    bool dp(int x, int y) {
        if (f[x][y] != -1)  return f[x][y];
        if (y == m) return f[x][y] = (x == n);//如果匹配到最后一个；
        if (p[y + 1] == '*') f[x][y] = dp(x, y + 2) || dp(x + 1, y);//p[y + 1]的情况。
        else if (p[y] == '.' && x < n) f[x][y] = dp(x + 1, y + 1);//不要忘记x < n, 我忘记了。
        else {//p[y + 1]既不是‘*’，也不是'.'的情况。
            if (s[x] == p[y]) f[x][y] = dp(x + 1, y + 1);
            else f[x][y] = false;
        }
        return f[x][y];
    }
};