题解 | #字符串通配符#动态规划

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

int main() {
	string a, b;
	cin >> a >> b;
	int lena = a.size();
	int lenb = b.size();
	for (int i = 0; i < lena; i++)
		if (a[i] >= 'A'&&a[i] <= 'Z') a[i] = a[i] - 'A' + 'a';
	for (int i = 0; i < lenb; i++)
		if (b[i] >= 'A'&&b[i] <= 'Z') b[i] = b[i] - 'A' + 'a';
	vector<vector<int>>dp(lena + 1, vector<int>(lenb + 1, 0));
	dp[0][0] = 1;
	for (int j = 1; j <= lenb; j++) dp[0][j] = 0;
	for (int i = 1; i <= lena; i++)
		if (a[i - 1] == '*') dp[i][0] = dp[i - 1][0];
	for(int i=1;i<=lena;i++)
		for (int j = 1; j <= lenb; j++) {
			if (a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1];
			else {
				if (!(b[j - 1] >= 'a'&&b[j - 1] <= 'z' || b[j - 1] >= '0'&&b[j - 1] <= '9')) dp[i][j] = 0;
				else if (a[i - 1] == '*') dp[i][j] = max(dp[i - 1][j - 1], max(dp[i - 1][j], dp[i][j - 1]));
				else if (a[i - 1] == '?') dp[i][j] = dp[i - 1][j - 1];
				else dp[i][j] = 0;
			}
		}
	if(dp[lena][lenb])
	cout << "true";
	else cout << "false";
}