题目
请实现一个函数用来匹配包括’.’和’‘的正则表达式。
模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（含0次）。
在本题中，匹配是指字符串的所有字符匹配整个模式。
例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”aba”均不匹配。
样例
输入：
s=”aa”
p=”a“
输出:true

解法一：模拟

需要注意一下的处理
大循环结束后，字符串s必须得匹配完，模式串可以不匹配到结束，但是这种情况要求下一位必须得是（测试得出，最初以为模式串也得匹配完）
时间复杂度O(n+m)，空间复杂度O(1)

class Solution {
public:
    bool isMatch(string s, string p) {
        int i = 0, j = 0;
        while (i < s.size() && j < p.size()) {
            if (s[i] == p[j] || p[j] == '.') {
                i++;
                if (!(j + 1 < p.size() && p[j + 1] == '*')) {
                    j++;
                }
            }
            else if (p[j] == '*') {
                j++;
            }
            else if (j + 1 < p.size() && p[j + 1] == '*') {
                j++;
            }
            else {
                // cout << i << ' ' << j << endl;
                return false;
            }
        }
        if (i == s.size() && (j == p.size() || (p[j + 1] == '*')))
            return true;
        // cout << i << ' ' << s.size() << ' ' << j << ' ' << p.size() << endl;
        return false;
    }
};

解法二：动态规划

字符串匹配之类问题都可以用动态规划去做
f[i][j]表示字符串s从i到结尾，模式串p从j到结尾的匹配情况

• p[j+1]不是*
  • (s[i] == p[j] || p[j] == ‘.’) && f[i+1][j+1]
• p[j+1]是*
  • p[j]零次匹配：考察f[i][j+2]
  • p[j]多次匹配：(s[i] == p[j] || p[j] == ‘.’) && 考察f[i+1][j]

时间复杂度O(mn)，空间复杂度O(mn)

class Solution {
public:
    int n, m;
    vector<vector<int>> f;
    bool isMatch(string s, string p) {
        n = s.size(), m = p.size();
        f = vector<vector<int>>(n + 1, vector<int>(m + 1, -1));
        return dp(0, 0, s, p);
    }
    bool dp(int x, int y, const string &s, const string &p) {
        if (f[x][y] != -1) return f[x][y];
        if (y == m) {
            return f[x][y] = x == n;
        }
        bool first_match = x < n && (s[x] == p[y] || p[y] == '.');
        if (y + 1 < m && p[y + 1] == '*') {
            f[x][y] = dp(x, y + 2, s, p) || first_match && dp(x + 1, y, s, p);
        }
        else {
            f[x][y] = first_match && dp(x + 1, y + 1, s, p);
        }
        return f[x][y];
    }
};