#include <bits/stdc++.h> #include <cctype> using namespace std; int main() { string input1, input2; cin >> input1 >> input2; int n1 = input1.size(); int n2 = input2.size(); vector<vector<bool>> DP(n1 + 1, vector<bool>(n2 + 1, false)); DP[0][0] = true; int i, j; for (i = 0; i < n1; i++) { for (j = 0; j < n2; j++) { if (DP[i][j] == false) continue; if (input1[i] == '*') { int dis = 0; while ((j + dis <= n2) && (isalpha(input2[j]) || isdigit(input2[j]))) { DP[i+1][j + dis] = true; dis++; } } else if (input1[i] == '?') { if (isdigit(input2[j]) || isalpha(input2[j])) { DP[i+1][j+1] = true; } } else if (isalpha(input1[i])) { if (isalpha(input2[j]) && tolower(input1[i]) == tolower(input2[j])) { DP[i+1][j+1] = true; }; } else if (input1[i] == input2[j]) { DP[i+1][j+1] = true; } } } if(DP[n1][n2]){ cout<<"true"; }else{ cout<<"false"; } // cout<<DP[n1][n2]; } // 64 位输出请用 printf("%lld")
思路请看上面链接,这里直接解析代码。使用二维DP数组来记录DP[i][j]表示串1的前i个字符和串2的前j个字符是否匹配
初始化:DP[s1.size()+1][s2.size()+1] ,DP[0][0]=true;
二维循环,先遍历串1,在遍历串2 。