LeetCode 44 Wildcard Matching

    
        标签：
        
            LeetCode
        
    发布于：2021-05-28 10:59:26
    编辑于：2021-05-28 20:13:14
    浏览量：1008

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) 的解法

https://leetcode.com/problems/wildcard-matching/discuss/17810/Linear-runtime-and-constant-space-solution

还没好好看，先标记了。

Links: leetcode-44-wildcard-matching