采用动态规划 状态转移： dp[i][j] 表示 s的前i个与p的前j个是否匹配

那么有以下几个转换状态

1 p[j-1] 是字母 而且与 s[i-1] 相等，那么当前dp[i][j]是否匹配就依赖于dp[i-1][j-1]

2 p[j-1] 是. 那么肯定与s[i-1]相等， 当前dp[i][j]是否匹配 就依赖于 dp[i-1][j-1] 情况1 2 类似 可以在代码中一起判断

3 p[j-1] 是 那么根据 表示的前面字母的多次重复还是0次重复 分为两种情况

3.1 如果是0次重复 那么当前的p[j-1] == ‘*’ 和 p[j-2] 都可以忽略不计。 那么 dp[i][j] = dp[i]j-2

3.2 如果是多次重复 那么 p[j-2] 与s[i-1] 相等 或者p[j-2]==’.’ 那么dp[i][j] = dp[i-1][j]

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int dp[N][N];

void solve(string s, string p) {
    memset(dp, 0, sizeof(dp));
    int m = s.size(), n = p.size();
    dp[0][0] = 1;
    for(int j=2;j<=n;j++){
        if(p[j-1]=='*'){
            dp[0][j]=dp[0][j-2];
        }
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(s[i-1]==p[j-1]||p[j-1]=='.'){
                dp[i][j]=dp[i-1][j-1];
            }
            else if(p[j-1]=='*'){
                if(s[i-1]==p[j-2]||p[j-2]=='.'){
                    dp[i][j]=dp[i-1][j]||dp[i][j-2];
                }
                else{
                    dp[i][j]=dp[i][j-2];
                }
            }
        }
    }
   if(dp[m][n]) cout << "true";
   else cout << "false";
}

int main() {
    string s, p;
    cin >> s >> p;
    solve(s,p);
    return 0;
}