HJ71 字符串通配符

HJ71 字符串通配符

题目：https://www.nowcoder.com/practice/43072d50a6eb44d2a6c816a283b02036?tpId=37&tqId=21294&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D37&difficulty=undefined&judgeStatus=undefined&tags=&title=

先读入两个字符串a,b，然后进行大小写转换，统一转化成小写。字符串下标从1开始存储。dp[i][j]表示对于a的前i位字符串和b的前j位字符串是否能匹配，如果可以则为1，否则为0。

处理边界情况：dp[0][0]=1;即两串字符串都为空字符串时是匹配的。然后for(int i=1;i<=la;i++)if(a[i]=='*')dp[i][0]=1;else break;由于*可以对应空字符串，所以***的情况是可以和空字符串匹配的，所以要预处理为1.

状态转移方程：

- `a[i] == b[j]` 或 `a[i] == '?'` 且 `b[j]` 是合法字符时，`dp[i][j] = dp[i-1][j-1]`。
- `a[i] == '*'` 且 `b[j]` 是合法字符时：
- `dp[i][j] = dp[i-1][j-1]`：`*`匹配一个字符
- `dp[i][j] = dp[i][j-1]`：`*`匹配多个字符
- `dp[i][j] = dp[i-1][j]`：`*`匹配空字符

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 char a[110],b[110];
 4 int la,lb,dp[110][110];
 5 bool Check(char c){
 6     if(c>='a'&&c<='z')return 1;
 7     if(c>='0'&&c<='9')return 1;
 8     return 0;
 9 }
10 int main(){
11     scanf("%s",a+1);
12     scanf("%s",b+1);
13     la=strlen(a+1); lb=strlen(b+1);
14     for(int i=1;i<=la;i++)
15         if(a[i]>='A'&&a[i]<='Z')a[i]=a[i]-'A'+'a';
16     for(int i=1;i<=lb;i++)
17         if(b[i]>='A'&&b[i]<='Z')b[i]=b[i]-'A'+'a';
18     dp[0][0]=1;
19     for(int i=1;i<=la;i++) if(a[i]=='*')dp[i][0]=1;else break;
20     for(int i=1;i<=la;i++){
21         for(int j=1;j<=lb;j++){
22             if(a[i]==b[j])dp[i][j]=max(dp[i][j],dp[i-1][j-1]);
23             else if(a[i]=='?'&&Check(b[j]))dp[i][j]=max(dp[i][j],dp[i-1][j-1]);
24             else if(a[i]=='*'&&Check(b[j])){
25                 dp[i][j]=max(dp[i][j],dp[i-1][j-1]);
26                 dp[i][j]=max(dp[i][j],dp[i][j-1]);
27                 dp[i][j]=max(dp[i][j],dp[i-1][j]);
28             }
29         }
30     }
31     if(dp[la][lb])puts("true");else puts("false");
32 }

by:AlenaNuna