这一题比赛的时候试图暴力结果还WA了。正解是用DP, dp[i][j]表示第一个字符串s1前i位和第二个字符串s2前j位是否匹配。如果当前状态[i,j]不匹配，那么也无法向后转移到匹配的状态。
如果[i,j]匹配且s1[i+1]==s2[j+1]，那么[i+1,j+1]也匹配。
如果[i,j]匹配且s1[i+1]=='*'，那么[i+1,j],[i+1,k]匹配，k是j+1及其之后4个非*的字符。必须排除*是因为*可能是空字符。
如果[i,j]匹配且s2[j+1]=='*'，那么[i,j+1],[k,j+1]匹配，k是i+1及其之后4个非*的字符。
开始出错是因为这里的状态转移不一定相邻的index转移的。并不能由dp[i-1][j-1]==1直接的出dp[k][j]=1。例如shakes和*，在第一次循环中得出shak与*匹配，之后再循环到pair(e,*)时，就会因为(k,*)匹配而认为(e,*)匹配。
#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<string>
#include<cmath>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
//2018 Round A Problem B large data
int T;
const int maxn=2010;
string s1;
string s2;
int dp[maxn][maxn];
void solve()
{
dp[0][0]=1;
for(int i=0;i<s1.length();i++)
{
for(int j=0;j<s2.length();j++)
{
if(dp[i][j]==0) continue;
if(s1[i+1]==s2[j+1]&&s1[i+1]!='*'&&s2[j+1]!='*')
{
dp[i+1][j+1]=1;
}
if(s1[i+1]=='*')
{
int cnt=0;
int k=j;
while(cnt<4&&k<s2.length())
{
if(k>j&&s2[k]!='*')
{
cnt++;
}
dp[i+1][k]=1;
k++;
}
}
if(s2[j+1]=='*')
{
int cnt=0;
int k=i;
while(cnt<4&&k<s1.length())
{
if(k>i&&s1[k]!='*')
{
cnt++;
}
dp[k][j+1]=1;
k++;
}
}
}
}
// for(int i=0;i<s1.length();i++)
// {
// for(int j=0;j<s2.length();j++)
// {
// cout<<dp[i][j]<<" ";
// }
// cout<<endl;
// }
}
int main()
{
// char s[maxn];
// scanf("%s",s+1);
// cout<<strlen(s+1)<<" "<<strlen(s)<<endl;
freopen("B-large-practice.in","r",stdin);
// freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%d",&T);
for(int ca=1;ca<=T;ca++)
{
memset(dp,0,sizeof(dp));
cin>>s1>>s2;
s1="A"+s1;
s2="A"+s2;
solve();
printf("Case #%d: %s\n",ca,dp[s1.length()-1][s2.length()-1]==1?"TRUE":"FALSE");
}
return 0;
}
//WA: q* q; q* qabc****d; q*e qabc*de
小数据dfs暴力代码如下。WA就是因为对于s1[i]=*时，直接枚举s2[j] to s2[j+4]，没有排除s2[j+k]='*'的字符。另一处是dfs终点，如果其中一个字符串达到末尾，另一个字符还剩下不超过4个non-* character就返回true。
#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<string>
#include<cmath>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
//2018 Round A Problem B small data
int T;
const int maxn=2010;
char s1[maxn];
char s2[maxn];
bool dfs(int x,int y)
{
// cout<<x<<" "<<y<<endl;
// if(x>=strlen(s1)&&y>=strlen(s2))
// {
// return false;
// }
// cout<<x<<" "<<strlen(s1)-1<<s1[x]<<endl;
if(x==strlen(s1)-1&&y==strlen(s2)-1)
{
if(s1[x]=='*'||s2[y]=='*'||s1[x]==s2[y])
{
return true;
}
return false;
}
if(x==strlen(s1)-1&&s1[x]=='*')
{
// cout<<s1[x]<<" "<<y<<" "<<endl;
if(y+4>=strlen(s2))
{
return true;
}
else
{
int cnt=strlen(s2)-y;
for(int i=y;i<strlen(s2);i++)
{
if(s2[i]=='*')
{
cnt--;
}
}
if(cnt<=4)
{
return true;
}
}
return false;
}
if(y==strlen(s2)-1&&s2[y]=='*')
{
if(x+4>=strlen(s1))//can not use x>=strlen(s1)-4, the type of strlen is not int
{
return true;
}
else
{
int cnt=strlen(s1)-x;
for(int i=y;i<strlen(s1);i++)
{
if(s1[i]=='*')
{
cnt--;
}
}
if(cnt<=4)
{
return true;
}
}
return false;
}
bool ret=false;
if(s1[x]=='*')
{
// cout<<"here"<<endl;
int i=0;
for(int cnt=0;cnt<=4;)
{
if(y+i>=strlen(s2)) return false;
if(dfs(x+1,y+i)==true)
{
ret=true;
return true;
//break;
}
if(s2[y+i]!='*')
{
cnt++;
}
i++;
}
}
if(s2[y]=='*')
{
int i=0;
for(int cnt=0;cnt<=4;)
{
// cout<<x<<" a "<<y<<" "<<i<<endl;
if(x+i>=strlen(s1)) return false;
if(dfs(x+i,y+1)==true)
{
ret=true;
return true;
//break;
}
if(s1[x+i]!='*')
{
// cout<<x<<" b "<<i<<endl;
cnt++;
}
i++;
}
}
if(s1[x]!='*'&&s2[y]!='*')
{
if(s1[x]!=s2[y])
{
return false;
}
while(s1[x]==s2[y]&&s1[x]!='*'&&s2[y]!='*')
{
x++;
y++;
if(x==strlen(s1)&&y==strlen(s2))
{
return true;
}
// cout<<x<<" a "<<y<<endl;
}
ret=dfs(x,y);
}
return ret;
}
int main()
{
freopen("B-large-practice.in","r",stdin);
// freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%d",&T);
for(int ca=1;ca<=T;ca++)
{
memset(s1,0,sizeof(s1));
memset(s2,0,sizeof(s2));
scanf("%s %s",&s1,&s2);
printf("Case #%d: %s\n",ca,dfs(0,0)==true?"TRUE":"FALSE");
}
return 0;
}
//WA: q* q; q* qabc****d; q*e qabc*de