題目鏈接 Problem Description Giving two strings and you should judge if they are matched.The first string contains lowercase letters and uppercase letters ...
Problem Description Giving two strings and you should judge if they are matched.
The first string contains lowercase letters and uppercase letters.
The second string contains lowercase letters, uppercase letters, and special symbols: “.” and “*”.
. can match any letter, and * means the front character can appear any times. For example, “a.b” can match “acb” or “abb”, “a*” can match “a”, “aa” and even empty string. ( “*” will not appear in the front of the string, and there will not be two consecutive “*”.
Input The first line contains an integer T implying the number of test cases. (T≤15)
For each test case, there are two lines implying the two strings (The length of the two strings is less than 2500).
Output For each test case, print “yes” if the two strings are matched, otherwise print “no”.
Sample Input 3 aa a* abb a.* abb aab
Sample Output yes yes no 題意：給了兩個字元串，判斷是否匹配。第一個串只包含小寫和大寫字元，第二個串包含小寫、大寫字元，還包括‘ . ’和' * '，' . ' 可以匹配任意一個字元，' * ' 表示' * '之前的字元可以重覆多次，比如a*可以匹配a、aa、aa……以及空串（註：第二個串不會以' * '開始，也不會有兩個連續的' * '）。 思路：考慮DP，每次根據１～ｉ的ｂ串能使ａ串到達哪些位置，進而推出１～ｉ＋１的ｂ串能使ａ串到達哪些位置。 代碼如下：
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; const int N=2505; char a[N],b[N]; int len1,len2; int dp[N][N]; int main() { int T; cin>>T; while(T--){ scanf("%s%s",a+1,b+1); len1=strlen(a+1); len2=strlen(b+1); memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=1;i<=len2;i++) { if(b[i]=='.') { for(int j=0;j<=len1;j++) { if(dp[i-1][j]) dp[i][j+1]=1; } } else if(b[i]=='*') { for(int j=0;j<=len1;j++) { if(dp[i-1][j]) { dp[i][j]=1; dp[i][j-1]=1; while(a[j+1]==a[j]) dp[i][j+1]=1,j++; } } } else { for(int j=0;j<=len1;j++) { if(!dp[i-1][j]) continue; if(a[j+1]==b[i]) dp[i][j+1]=1; else if(b[i+1]=='*') dp[i+1][j]=1; } } } if(dp[len2][len1]) puts("yes"); else puts("no"); } return 0; } /* .*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.* */
比賽中我用的深搜模擬的，會超時，但是如果答案是＂yes＂的話，會很快的計算出，不會超時；如果是” no "的話，會搜索所有的情況，會超時，這個時候我們可以用一個變數記錄一下遞歸次數，當大於一定次數時預設為“no”的情況，退出搜索。（當然這種做法不是正解，腦洞大開，如果有厲害的數據肯定過不了~）
代碼如下：
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; const int N=2505; char a[N],b[N]; int len1,len2; int h[N]; int c; int dfs(int i,int j) { c++; if(c>1000000) return 0;///預設為"no"的情況； if(i<len1 && j>=len2) return 0; if(i>=len1){ if(j>=len2) return 1; if(j==len2-1 && b[j]=='*') return 1; if(j==len2-1 && b[j]!='*') return 0; if(j<len2-1){ if(b[j]=='*' && h[j+1]) return 1; else if(b[j]!='*' && h[j]) return 1; else return 0; } } if(b[j]=='.') { b[j]=a[i]; int f=dfs(i+1,j+1); b[j]='.'; return f; } if(b[j]=='*') { if(a[i]==b[j-1]){ if(dfs(i+1,j)) return 1; if(dfs(i,j+1)) return 1; if(dfs(i-1,j+1)) return 1; } else { if(dfs(i-1,j+1)) return 1; if(dfs(i,j+1)) return 1; } } if(a[i]==b[j]) return dfs(i+1,j+1); else if(b[j+1]=='*') return dfs(i,j+2); else return 0; } int main() { int T; cin>>T; while(T--){ scanf("%s%s",a,b); c=0; len1=strlen(a); len2=strlen(b); int flag=1; for(int i=len2-1;i>=0;i--) { if(!flag) h[i]=0; else if(b[i]=='*'){ h[i]=1; h[i-1]=1; i--; } else{ h[i]=0; flag=0; } } int ans=dfs(0,0); if(ans) puts("yes"); else puts("no"); } return 0; } /* .*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.* */
