题解 | 字符串通配符
字符串通配符
https://www.nowcoder.com/practice/43072d50a6eb44d2a6c816a283b02036
#include <iostream> #include <vector> #include <cctype> using namespace std; bool isMatch(const string& s, const string& p) { int m = s.length(); int n = p.length(); //dp[i][j] 表示s的前i个字符是否匹配p的前j个字符 vector<vector<bool> > dp(m+1, vector<bool>(n+1, false)); //初始化 dp[0][0] = true; //检测s里面有没有* 因为*也能匹配空字符串 for(int i = 0; i < m; ++i) { if(s[i] == '*') { dp[i+1][0] = dp[i][0]; } } //填充dp数组 for(int i = 1; i <= m; ++i) { for(int j = 1; j <= n; ++j) { if(s[i-1] == '*') { if(isalnum(p[j-1])) { //是数字和字母的话 *可以为空也可以匹配p[j-1] dp[i][j] = dp[i-1][j] || dp[i][j-1]; } else { //不是数字或者字母的话 *就只能为空了 dp[i][j] = dp[i-1][j]; } } else if(s[i-1] == '?') { if(isalnum(p[j-1])) { dp[i][j] = dp[i-1][j-1]; } else dp[i][j] = false; } else { //如果是数字或其他特殊字符会返回其本身 只有是大写字母时才会发生改变返回小写字符 if(tolower(s[i-1]) == tolower(p[j-1])) { dp[i][j] = dp[i-1][j-1]; } else dp[i][j] = false; } } } return dp[m][n]; } int main() { string s, p; cin >> s >> p; cout << (isMatch(s, p) ? "true" : "false") << endl; return 0; }