题解 | 字符串通配符（简单dp）

#牛客春招刷题训练营# + 链接

dp[i][j]表示s串前i个字符跟p串前j个字符是否匹配，简单处理一下'*'字符和'?'字符。

比较坑的是s串前缀的'*'字符需要特殊考虑。

#include <bits/stdc++.h>
using namespace std;

const int MAXN=128;
char x[MAXN],y[MAXN];
bool dp[MAXN][MAXN];

bool ab(char c)
{
    return ('a'<=c && c<='z') || ('0'<=c && c<='9');
}

int main() {
    scanf("%s",(x+1));
    scanf("%s",(y+1));
    int n = strlen(x+1), m = strlen(y+1);
    for (int i=1;i<=n;i++) {
        if ('A'<=x[i] && x[i]<='Z') x[i] = x[i]-'A'+'a';
    }
    for (int j=1;j<=m;j++) {
        if ('A'<=y[j] && y[j]<='Z') y[j] = y[j]-'A'+'a';
    }
    dp[0][0] = 1;
    for (int i=1;i<=n && x[i]=='*';i++) {
        dp[i][0]=1;
    }
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            if (x[i]=='*' && ab(y[j])) {
                dp[i][j]|=dp[i-1][j];
                dp[i][j]|=dp[i][j-1];
                dp[i][j]|=dp[i-1][j-1];
            }
            if (x[i]=='?' && ab(y[j])) {
                dp[i][j]|=dp[i-1][j-1];
            }
            if (x[i]==y[j]) {
                dp[i][j]|=dp[i-1][j-1];
            }
        }
    }
    if (dp[n][m]) puts("true");
    else puts("false");
    return 0;
}