A38313. 带通配符的字符串匹配通配符是一类键盘字符， 当我们不知道真正字符或者不想键入完整名字时， 常常使用通配符代替一个或多个真正字符。 通配符有问号(?)和星号(*)等， 其中， “?”可以代替一个字符， 而“*”可以代替零个或多个字符。你的任务是， 给出一个带有通配符的字符串和一个不带通配符的字符串， 判断他们是否能够匹配。例如， 1 ?456 可以匹配 1 2456、 1 3456、 1 a456…
填空题
困难
知识点
题目描述
带通配符的字符串匹配
通配符是一类键盘字符， 当我们不知道真正字符或者不想键入完整名字时， 常常使用通配符代替一个或多个真正字符。 通配符有问号(?)和星号(*)等， 其中， “?”可以代替一个字符， 而“*”可以代替零个或多个字符。你的任务是， 给出一个带有通配符的字符串和一个不带通配符的字符串， 判断他们是否能够匹配。
例如， 1 ?456 可以匹配 1 2456、 1 3456、 1 a456， 但是却不能够匹配 23456、 1 aa456；2*77?8 可以匹配 24457798、 237708、 27798。
输入
输入有两行， 每行为一个不超过 20 个字符的字符串， 第一行带通配符， 第二行不带通配符
输出
如果两者可以匹配， 就输出“matched”， 否则输出“not matched”
样例输入
1*456?
11111114567
样例输出
matched
参考答案
#include<iostream>
#include<string>
using namespace std;
bool dp[30][30] = {
}
;
int main() {
string s1,s2;
cin >> s1 >> s2;
int n1 = s1.size(), n2 = s2.size();
dp[0][0] = true;
int i=0, j=0;
for (i=1; s1.at(i-1)=='*'; i++) // 第二行可能会是空字符串,空字符串可以与任意多的*匹配 {
dp[i][0] = true;
}
for (i=1; i<=n1; i++) {
for (j=1; j<=n2; j++) {
if (s1.at(i-1)=='*' && (dp[i-1][j-1]||dp[i][j-1]||dp[i-1][j]))
// dp[i-1][j-1]对应*匹配到的第一个字符
// dp[i][j-1]对应*匹配到的第二个以后的字符
// dp[i-1][j]对应*匹配到空字符 {
dp[i][j] = true;
} else if (s1.at(i-1)=='?' && dp[i-1][j-1]) {
dp[i][j] = true;
} else if (s1.at(i-1)==s2.at(j-1) && dp[i-1][j-1]) {
dp[i][j] = true;
}
}
}
if (dp[n1][n2]) {
cout << "matched";
} else {
cout << "not matched";
}
return 0;
}
上一题
下一题