为了描述方便,我们将
s
称为主串,p
称为模式串
三种思路:
- 贪心(超时)
- 回溯
- 动态规划
贪心(超时)
// // Created by jt on 2020/8/31. // #include <cstring> #include <iostream> using namespace std; class Solution { public: bool isMatch(const char *s, const char *p) { return greedy(s, p, 0, 0); } bool greedy(const char *s, const char *p, int idxS, int idxP) { if (idxS >= strlen(s) && idxP >= strlen(p)) return true; if (idxS >= strlen(s) || idxP >= strlen(p)) return false; if (s[idxS] == p[idxP] || p[idxP] == '?') return greedy(s, p, idxS+1, idxP+1); if (p[idxP] == '*') { for (int i = idxS; i < strlen(s); ++i) { if (greedy(s, p, i, idxP + 1)) return true; } } return false; } };
回溯:当模式为*
时,不断延长*
对主串的覆盖长度,然后继续比对剩余部分,主要逻辑如下——
- 如果两个字符匹配或者模式串对应的字符为
?
时,将两个指针都加1 - 如果模式串的字符为
*
时,记录*的位置
以及主串的位置
,将模式串指针
前进一步 - 如果字符不匹配,且模式串的字符不为
*
,但是记录过*的位置
,将模式串指针
重置为*位置的下一个位置
,同时将主串的旧位置
前进一步,并更新主串的位置
// // Created by jt on 2020/8/31. // #include <iostream> using namespace std; class Solution { public: bool isMatch(const char *s, const char *p) { const char* star=NULL; const char* ss=s; while (*s){ // 当(两个字符匹配)或(模式串的字符为'?')时,将两个指针同时前进一步 // 注意p不会超出字符串的长度 if ((*p=='?')||(*p==*s)){s++;p++;continue;} // 模式串的字符为'*'时,记录'*'的位置与s的位置,并且只让模式串的指针前进一步 if (*p=='*'){star=p++; ss=s;continue;} // 如果当前字符不匹配,最后一个指针是'*',当前模式指针非'*' // 只让模式串的指针前进一步 if (star){ p = star+1; s=++ss;continue;} // 当前模式指针指向非'*',最后一个模式串指针非'*',且字符不匹配 return false; } // 检查模式中剩余字符 while (*p=='*'){p++;} return !*p; } };
动态规划
dp[i][j]表示主串前i个字符和匹配串前j个字符的匹配结果,状态公式如下:
- 如果
s[i-1]==p[j-1] || p[j-1]=='?'
,那么dp[i][j]=dp[i-1][j-1]
- 如果
p[j-1]=='*'
,那么dp[i][j] = any(dp[1..i][j-1])
- 如果
s[i-1]!=p[j-1] && (p[j-1]!='*' || p[j-1]!='?')
,那么dp[i][j]=false
- 基准1:
dp[0][0]=true
- 基准2:
dp[0][1..k]=true
(如果p[0..k-1]
中只含有*
),或dp[0][k+1..]=false
(如果p[0..k-1]
中只含有*
,但p[k]
不为*
) - 基准3:
dp[1..][0]=false
解释如下:
- 如果当前字符匹配,那么是否匹配取决于各自子串
- 如果模式串当前字符为
*
,那么是否匹配取决于主串中是否存在子串能与p[0..j-1]匹配上 - 如果当前字符不匹配,且模式串中当前字符不为
*
或?
,那么恒不匹配 - 基准1: 两个空串匹配
- 基准2: 如果主串为空且p[..]中只含有
*
,匹配;如果主串为空且p[..]中不仅含有*
,不匹配; - 基准3: 如果主串非空,模式串为空,不匹配
代码如下:
// // Created by jt on 2020/8/31. // #include <vector> #include <cstring> using namespace std; class Solution { public: bool isMatch(const char *s, const char *p) { int sLen = strlen(s), pLen = strlen(p); vector<vector<bool> > dp(sLen + 1, vector<bool>(pLen + 1, true)); for (int i = 1; i <= sLen; ++i) { dp[i][0] = false; } for (int i = 0; i < pLen; ++i) if (p[i] != '*') { for (int j = i + 1; j<= pLen; ++j) dp[0][j] = false; break; } for (int i = 1; i <= sLen; ++i) { for (int j = 1; j <= pLen; ++j) { dp[i][j] = false; if (s[i-1] == p[j-1] || p[j-1] == '?') dp[i][j] = dp[i-1][j-1]; else if (p[j-1] == '*') { dp[i][j] = dp[i-1][j-1] || dp[i][j-1] || dp[i-1][j]; } } } return dp[sLen][pLen]; } };