JustSong Archive Link About
Projects
Categories
Others

LeetCode 44 Wildcard Matching

Tag: LeetCode 回溯法 Posted on 2020-06-10 13:06:15 Edited on 2020-06-10 17:00:28 Views: 124

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;
    }
}

分支数目太多,需要剪枝。

未经允许,禁止转载,本文源站链接:https://iamazing.cn/