LeetCode 44 Wildcard Matching
https://leetcode.com/problems/wildcard-matching/
这是一道 hard 题，基本思路很简单，套回溯法的框架就好，但是需要进行优化，不然会超时。
第一次尝试：WA
class Solution {
public:
string s;
string p;
bool isMatch(string s, string p) {
this->s = s;
this->p = p;
return backtrack(0, 0);
}
private:
bool backtrack(int si, int pi) {
if(si==s.size() && pi==p.size()) return true;
if(si==s.size() || pi==p.size()) return false;
if(p[pi]=='?' || s[si]==p[pi]) {
return backtrack(si+1, pi+1);
} else if(p[pi]=='*'){
for(int i=si;i<=s.size();i++) {
if(backtrack(i, pi+1)) return true;
}
}
return false;
}
};
这个是因为没考虑全 * 匹配空字符串的情况。
第二次尝试：RE
class Solution {
public:
string s;
string p;
bool isMatch(string s, string p) {
this->s = s;
this->p = p;
return backtrack(0, 0);
}
private:
bool backtrack(int si, int pi) {
if(si==s.size() && pi==p.size()) return true;
if(si<s.size() && pi==p.size()) return false; // 这里修改了
if(p[pi]=='?' || s[si]==p[pi]) {
return backtrack(si+1, pi+1);
} else if(p[pi]=='*'){
for(int i=si;i<=s.size();i++) {
if(backtrack(i, pi+1)) return true;
}
}
return false;
}
};
这个错的有点蠢，没有考虑到目标字符串已经匹配完毕而模式字符串还有的情况。
其实之前是考虑了的，只是改完之前的 bug 的后没有考虑到其对后续代码的影响。
第三次尝试：TLE
class Solution {
public:
string s;
string p;
bool isMatch(string s, string p) {
this->s = s;
this->p = p;
return backtrack(0, 0);
}
private:
bool backtrack(int si, int pi) {
if(si==s.size() && pi==p.size()) return true;
if(si<s.size() && pi==p.size()) return false;
if(si==s.size()) { // 这里修改了
for(int i=pi;i<p.size();i++) {
if(p[i]!='*') return false;
}
return true;
}
if(p[pi]=='?' || s[si]==p[pi]) {
return backtrack(si+1, pi+1);
} else if(p[pi]=='*'){
for(int i=si;i<=s.size();i++) {
if(backtrack(i, pi+1)) return true;
}
}
return false;
}
};
我们看一下当时的输入：
"aaabbbaabaaaaababaabaaabbabbbbbbbbaabababbabbbaaaaba"
"a*******b"
哦，原来是出现了一连串的 *，没问题，先对模式字符串进行预处理，删掉多余的 * 就好了么。
第四次尝试：TLE
class Solution {
public:
string s;
string p;
bool isMatch(string s, string p) {
this->s = s;
string p2; // 这里修改了
bool lastIsStar = false;
for(char c:p){
if(lastIsStar && c=='*') continue;
lastIsStar = c=='*';
p2 += c;
}
this->p = p2;
return backtrack(0, 0);
}
private:
bool backtrack(int si, int pi) {
if(si==s.size() && pi==p.size()) return true;
if(si<s.size() && pi==p.size()) return false;
if(si==s.size()) {
for(int i=pi;i<p.size();i++) {
if(p[i]!='*') return false;
}
return true;
}
if(p[pi]=='?' || s[si]==p[pi]) {
return backtrack(si+1, pi+1);
} else if(p[pi]=='*'){
for(int i=si;i<=s.size();i++) {
if(backtrack(i, pi+1)) return true;
}
}
return false;
}
};
艹，还是超时，当时的输入：
"abbabaaabbabbaababbabbbbbabbbabbbabaaaaababababbbabababaabbababaabbbbbbaaaabababbbaabbbbaabbbbababababbaabbaababaabbbababababbbbaaabbbbbabaaaabbababbbbaababaabbababbbbbababbbabaaaaaaaabbbbbaabaaababaaaabb"
"**aa*****ba*a*bb**aa*ab****a*aaaaaa***a*aaaa**bbabb*b*b**aaaaaaaaa*a********ba*bbb***a*ba*bb*bb**a*b*bb"
我在本地尝试跑了一下，快一分钟了还没出结果，有点佛。
这个显然原因在这里：
else if(p[pi]=='*'){
for(int i=si;i<=s.size();i++) {
if(backtrack(i, pi+1)) return true;
}
}
分支数目太多，需要剪枝。