给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符

‘*’ 匹配零个或多个前面的那一个元素

返回一个布尔值，表示匹配是否覆盖整个输入字符串（而非部分）。

示例 1：

**输入：**s = “aa”, p = “a”
**输出：**false
解释：“a” 无法匹配 “aa” 整个字符串。

示例 2:

**输入：**s = “aa”, p = “a*”
**输出：**true
**解释：**因为 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。

示例 3：

**输入：**s = “ab”, p = “.*”
**输出：**true
解释：".*" 表示可匹配零个或多个（’*’）任意字符（’.’）。

提示：

1 <= s.length <= 20

1 <= p.length <= 20

s 只包含从 a-z 的小写字母。

p 只包含从 a-z 的小写字母，以及字符 . 和 *。

保证每次出现字符 * 时，前面都匹配到有效的字符

使用动态规划逐步匹配

dp[i][j]表示s保留前i个字符与p保留前j个字符的结果，dp[0][0]表示s，p均为空默认为true

当i=0时，s为空串，此时p的每个字母或 . 后必须有*（匹配零个）

1
2
3
4
dp[0][0] = true;
for (int j = 2; j <= l2; j++) {
    dp[0][j] = p[j - 1] == '*' && dp[0][j - 2];
}

其他情况，当p[j-1]不为*时，直接判断

1
2
3
4
if (p[j - 1] != '*') {
    dp[i][j] = dp[i - 1][j - 1] &&
               (p[j - 1] == '.' || s[i - 1] == p[j - 1]);
}

当p[j-1]为*时先判断s[i-1]与p[j-2]是否匹配

匹配则同时考虑*号为重复0次（dp[i][j-2]）或多次（dp[i-1][j]）；

不匹配则先不考虑匹配 字母*，直接继承j-2的匹配结果；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool isMatch(string s, string p) {
        int l1 = s.size(), l2 = p.size();
        vector<vector<bool>> dp(l1 + 1, vector<bool>(l2 + 1, false));

        dp[0][0] = true;
        for (int j = 2; j <= l2; j++)
            dp[0][j] = p[j - 1] == '*' && dp[0][j - 2];
        for (int i = 1; i <= l1; i++) {
            for (int j = 1; j <= l2; j++) {
                if (p[j - 1] != '*')
                    dp[i][j] = dp[i - 1][j - 1] && (p[j - 1] == '.' || s[i - 1] == p[j - 1]);
                else {
                    if (p[j - 2] == '.' || s[i - 1] == p[j - 2])
                        dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
                    else
                        dp[i][j] = dp[i][j - 2];
                }
            }
        }
        return dp[l1][l2];
    }
};