Problem: 44. 通配符匹配
题目
给你一个输入字符串 (s) 和一个字符模式p ，请你实现一个支持 ‘?’ 和 ‘’ 匹配规则的通配符匹配：
‘?’ 可以匹配任何单个字符。
'’ 可以匹配任意字符序列（包括空字符序列）。
判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。
示例 1：
输入：s = “aa”, p = “a”
输出：false
解释：“a” 无法匹配 “aa” 整个字符串。
思路
两个思路 ，一种就是搜索dfs(代码超时，附上有心人优化)。另一种就是动态规划。文章来源：https://www.toymoban.com/news/detail-766639.html
假设 dp[i][j] 表示字符串s的前i字符和匹配串p的前j个字符的匹配结果。
分下面情况 ：文章来源地址https://www.toymoban.com/news/detail-766639.html
- 当 s[i] 和 p[j] 都是小写字母或者 p[j]是’?‘，如果p[j]=’?'是匹配的，如果s[i] = s[j] 也是匹配的。所以 这两种情况和dp[i-1][j-1]一样。
d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] dp[i][j] = dp[i-1][j-1] dp[i][j]=dp[i−1][j−1] - 当p[j]是‘*’ ：
(1) 匹配0个字符 : 相当于把p[j]去掉 d p [ i ] [ j ] = d p [ i ] [ j − 1 ] dp[i][j] = dp[i][j-1] dp[i][j]=dp[i][j−1]
(2) 匹配多个字符 ： 这个比较难理解 ，答案是 $ dp[i][j] = dp[i][j-1] $- 使用*。如 s = ‘abc’，p = ‘ab*’，或者 s = ‘abcd’, s = “abcde…”，*号能匹配0个或者多个任意字符。
- 对应的情况是’abcde’匹配’ab*‘，退一步’abcd’也能匹配’ab*’，‘abc’仍然能匹配’ab*’，‘ab’也能匹配’ab*’，'a’就不能匹配’ab*'了。
- 即 dp[i-1][j] = dp[i-2][j] | dp[i-3][j] … dp[0][j] 一直找下去, 由于i 是递增遍历的，每次答案都迭代进去了,所以省略了。
Code
class Solution {
public:
bool isMatch(string s, string p) {
// 动态规划
// dp[i][j] 表示s 的前i 个字符是否匹配p的前j 个字符
int m = s.size() ;
int n = p.size() ;
// 1. 当 s[i] 和 p[j] 都是小写字母
// 当 s[i] ==p[j] 时，dp[i][j] = dp[i-1][j-1]
// 当 s[i] !=p[j] 时 dp[i][j] = false ;
// 2。 当 p[j]是?
// dp[i][j] = dp[i-1][j-1] ;
// 3. 当p[j] 是 *
// (1) 当成空字符串 dp[i][j] = dp[i][j-1]
// (2) 使用星星 dp[i][j] = dp[i-1][j]
// 初始化
// dp[0][0] = True ;
// dp[i][] = false ;
// 特殊
vector<vector<int>> dp(m+1, vector<int>(n+1 )) ;
dp[0][0] = true ; // 空串一定匹配
for(int i = 1 ; i <=n ; i++ ) {
if(p[i-1] =='*') { // s: "" ,p: "*"
dp[0][i] = true ;
}else {
break ;
}
}
for(int i = 1 ; i<= m ; i++) {
for(int j = 1 ; j <=n ; 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-1]是匹配空字符
// dp[i-1][j] 是匹配多个字符
dp[i][j] = dp[i-1][j] | dp[i][j-1] ;
}
}
}
return dp[m][n] ;
}
};
DFS（超时）
class Solution {
public:
bool ans = false ;
set<pair<int,int>> memo;
void dfs(string s ,string p ,int pos1 ,int pos2 ) {
if(ans ) return ;
if(memo.count({pos1,pos2}) !=0) {
return ;
}
memo.insert({pos1,pos2}) ;
if(pos1 == s.size() && pos2 == p.size()) {
ans = true ;
return ;
}
while(pos1<s.size() && pos2<p.size() && (s[pos1] == p[pos2] || p[pos2]=='?') ){
pos1++ ;
pos2++ ;
}
if(pos1 == s.size() && pos2== p.size()) {
ans = true ;
return ;
}else if(p[pos2] =='*') {
// 粗去连续的*
while(pos2 <p.size() -1&& p[pos2+1] =='*') {
pos2++ ;
}
int cnt = 0 ;
while(pos1 + cnt <=s.size()) {
dfs(s,p,pos1+cnt++ , pos2+1) ;
}
}
}
bool isMatch(string s, string p) {
dfs(s,p,0,0) ;
return ans ;
}
};
到了这里，关于44. 通配符匹配（动态规划）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
