题目描述

请实现一个函数用来匹配包括’.’和’*’的正则表达式。

模式中的字符’.’表示任意一个字符，而’*’表示它前面的字符可以出现任意次（含0次）。

在本题中，匹配是指字符串的所有字符匹配整个模式。

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

样例

输入：

s="aa"
p="a*"

输出:true

算法

(动态规划)

1. 具体的算法步骤，推荐去看y总的视频讲解。这里简单说一些代码的注意点。
2. 为了方便，s和p均从1开始，s = ' + s，这个是字符串多方法，有大佬知道怎么作用于vector数组吗
3. 这里mark下二维数组vector的定义方式vector<vector<bool> > f(n + 1, vector<bool> (m + 1, 0))。
4. f[0][0] = true意味着空字符串与空字符串匹配，那么二者当然是互相匹配的
5. 接下来2重枚举，i从0开始因为s串是空字符串，p串中只要是-*的格式，也是可以匹配的，但是j从1开始是因为p串如果是空字符串，那么是不可能跟非空s串匹配的
6. 因为如果有*，一定要把*前面的字母和它看成是1体的，所以说先判断如果p[j + 1] = '*'，那么这个字母就不用看了，直接放到下一次迭代，直接来处理*是很香的。
7. 接下来，对于p[j] != '*'的情况，这样子p串就必须跟 非空s串才能匹配了，所以要i > 0，然后不要忘记s[i] == p[j可以匹配，p[j] == '.'也是可以匹的，我一开始就忘了这里。。
8. 如果p[j] == '*'，也要跟原先推出来的公式加上一个i > 0的条件，2个原因，f[i - 1]可能越界，s[i] == p[j - 1]，如果i为0，如果p[j]是*的话，p[j-1]一定是非空的，空不能匹配非空，所以这里也要求i > 0。
9. 最后要注意，else if()这里不能省条件写成else，因为上面的if中多判断了i，直接写else就错了，会SE。

时间复杂度

$O(n^3)$
$O(nm)$

C++ 代码

class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size(), m = p.size();
        s = ' ' + s, p = ' ' + p;

        // vector<vector<bool> > f(n, vector<bool> (m, 0));
        vector<vector<bool> > f(n + 10, vector<bool> (m + 10, false));
        f[0][0] = true;

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

        return f[n][m];
    }
};