判断两个字符串是否匹配(1个通配符代表一个字符) 【问题描述】 判断两个字符串是否匹配,其中一个字符串中包括通配符*,*可以代表任意一个非空字符。(其中每个字符串长度不超过100000);
时间: 2023-05-19 18:04:50 浏览: 69
可以使用动态规划来解决这个问题。定义一个二维数组dp[i][j]表示字符串s的前i个字符和模式p的前j个字符是否匹配。则有以下状态转移方程:
1. 如果p[j]是一个普通字符,那么只有当s[i]等于p[j]时,dp[i][j]才能为真,即dp[i][j] = dp[i-1][j-1]。
2. 如果p[j]是一个通配符,那么可以匹配任意一个非空字符,所以dp[i][j]可以从dp[i-1][j]或dp[i][j-1]转移而来,即dp[i][j] = dp[i-1][j] || dp[i][j-1]。
最终的答案即为dp[s.length()][p.length()]。时间复杂度为O(n^2),空间复杂度为O(n^2)。
以下是代码实现:
bool isMatch(string s, string p) {
int n = s.length(), m = p.length();
vector<vector<bool>> dp(n+1, vector<bool>(m+1, false));
dp[0][0] = true;
for (int i = 1; i <= m; i++) {
if (p[i-1] == '*') dp[0][i] = dp[0][i-1];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (p[j-1] == s[i-1] || p[j-1] == '?') {
dp[i][j] = dp[i-1][j-1];
} else if (p[j-1] == '*') {
dp[i][j] = dp[i-1][j] || dp[i][j-1];
}
}
}
return dp[n][m];
}
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)