题解 | #字符串通配符#
字符串通配符
https://www.nowcoder.com/practice/43072d50a6eb44d2a6c816a283b02036
#include<string> #include<iostream> #include<vector> using namespace std; int match_string(string s1, string s2) { vector<vector<int>> dp(s2.size() + 1, vector<int>(s1.size() + 1, 0)); //多加一行一列作为初始初值所用 dp[0][0] = 1;//初始化 for (int i = 1; i <= s2.size(); i++) { char ch1 = s2[i - 1]; ////设置每次循环的初值,即当星号不出现在首位时,匹配字符串的初值都为false dp[i][0] = dp[i - 1][0] && (ch1 == '*'); for (int j = 1; j <= s1.size(); j++) { char ch2 = s1[j - 1]; if (ch1 == '*') { dp[i][j] = dp[i - 1][j] || dp[i][j - 1]; //当匹配字符为*号时,可以匹配0个或者多个 } else { if (isalpha(ch2)) { //ch2为字母时,尝试是否能匹配 dp[i][j] = dp[i - 1][j - 1] && (ch1 == '?' || (ch2 == ch1 || ch2 == (ch1 + ('A' - 'a')) || ch2 == (ch1 - ('A' - 'a')))); } else if (isdigit(ch2)) { //ch2为数字时,尝试是否能匹配 dp[i][j] = dp[i - 1][j - 1] && (ch1 == '?' || (ch1 == ch2)); } else {//ch2既不为字母也不为数字时,只有ch1和ch2相同才能匹配 dp[i][j] = dp[i - 1][j - 1] && (ch1 == ch2); } } } } return dp[s2.size()][s1.size()]; } int main() { string str1, str2; while (cin >> str1 >> str2) { int flag = match_string(str2, str1); if (flag) { cout << "true" << endl; } else { cout << "false" << endl; } } }