LeetCode 44 Wildcard Matching
https://leetcode.com/problems/wildcard-matching/
分析
这道题大概一年前做过,TLE,淦。
暴力匹配法
这是我当初的解法,TLE。
TLE 时的输入为:
"babbbbaabababaabbababaababaabbaabababbaaababbababaaaaaabbabaaaabababbabbababbbaaaababbbabbbbbbbbbbaabbb"
"b**bb**a**bba*b**a*bbb**aba***babbb*aa****aabb*bbb***a"
该方法的思路是,首先对 pattern 进行预处理,像连在一起的 * 等价于单个 *。
之后就暴力匹配,遍历所有可能的路径。
暴力匹配没有剪枝,复杂度 O(n^2)。
代码:
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 isMatch(0, 0);
}
private:
bool isMatch(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]=='?' || p[pi]==s[si]) return isMatch(si+1, pi+1);
if(p[pi]=='*') return isMatch(si+1,pi) || isMatch(si,pi+1);
return false;
}
};
改进解法
改进点在于将 pattern 分割成一些子串,不再以字符为基本单位。 复杂度没变,还是 TLE 了,我淦。
class Solution {
public:
string s;
vector<string> ps;
bool isMatch(string s, string p) {
this->s = s;
string last;
bool lastIsStar = false;
for(char c : p){
if(lastIsStar) {
if(c=='*') {
last = "*";
continue;
} else {
lastIsStar = false;
ps.push_back(last);
last = c;
}
} else {
if(c=='*') {
lastIsStar = true;
// Notice this! "" & "*****"
if (last != "") ps.push_back(last);
last = c;
} else {
last += c;
}
}
}
// And this! "" & ""
if (last != "") ps.push_back(last);
return isMatch(0, 0);
}
private:
bool isMatch(int si, int pi) {
if(si==s.size() && pi==ps.size()) return true;
if(si<s.size() && pi==ps.size()) return false;
if(si==s.size()) {
for(int i=pi;i<ps.size();i++) {
if(ps[i]!="*") return false;
}
return true;
}
if (ps[pi] == "*") {
return isMatch(si+1, pi) || isMatch(si, pi+1);
} else {
// s[si:si+ps[pi].size()] == ps[pi]
if (s.size() - si < ps[pi].size()) return false;
for(int i=0;i<ps[pi].size();i++){
if (ps[pi][i] != s[si+i] && ps[pi][i] != '?') return false;
}
return isMatch(si+ps[pi].size(), pi+1);
}
}
};
改进解法 v2
上面解法有很多次重复的函数调用,加了个 dp,终于过了。
早该想到的,淦!
44 ms 27.3 MB
class Solution {
public:
string s;
vector<string> ps;
vector<vector<int>> dp;
bool isMatch(string s, string p) {
this->s = s;
string last;
bool lastIsStar = false;
for(char c : p){
if(lastIsStar) {
if(c=='*') {
last = "*";
continue;
} else {
lastIsStar = false;
ps.push_back(last);
last = c;
}
} else {
if(c=='*') {
lastIsStar = true;
// Notice this! "" & "*****"
if (last != "") ps.push_back(last);
last = c;
} else {
last += c;
}
}
}
// And this! "" & ""
if (last != "") ps.push_back(last);
vector<vector<int>> temp(s.size(), vector<int>(ps.size(), -1));
dp = temp;
return isMatch(0, 0);
}
private:
bool isMatch(int si, int pi) {
if(si==s.size() && pi==ps.size()) return true;
if(si<s.size() && pi==ps.size()) return false;
if(si==s.size()) {
for(int i=pi;i<ps.size();i++) {
if(ps[i]!="*") return false;
}
return true;
}
if (dp[si][pi] != -1) return dp[si][pi] == 1;
bool res = false;
if (ps[pi] == "*") {
res = isMatch(si+1, pi) || isMatch(si, pi+1);
} else {
// s[si:si+ps[pi].size()] == ps[pi]
if (s.size() - si < ps[pi].size()) {
dp[si][pi] = 0;
return false;
}
for(int i=0;i<ps[pi].size();i++){
if (ps[pi][i] != s[si+i] && ps[pi][i] != '?') {
dp[si][pi] = 0;
return false;
}
}
res = isMatch(si+ps[pi].size(), pi+1);
}
if (res) {
dp[si][pi] = 1;
} else {
dp[si][pi] = 0;
}
return res;
}
};
O(m*n) 的解法
还没好好看,先标记了。