Leetcode 44 Wildcard Matching 通配符匹配

SimonMa 發(fā)布于2019-08-14 17:16 / 1495人閱讀

摘要：難度題目給出一個(gè)字符串和一個(gè)要求我們給出這個(gè)字符串是否匹配這個(gè)其中通配符跟我們平常見到的一樣是和代表任意單個(gè)字符代表一個(gè)或多個(gè)字符這個(gè)題跟簡(jiǎn)單正則匹配比較類似可以跟這里面第二個(gè)解法一樣采取類似的動(dòng)態(tài)規(guī)劃解法在里取中間某個(gè)確定的字符串序列將字

Implement wildcard pattern matching with support for "?" and "*".

"?" Matches any single character.
 "*" Matches any sequence of
characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
 bool isMatch(const char *s,
const char *p)

Some examples:
 isMatch("aa","a") → false
 isMatch("aa","aa") → true
 isMatch("aaa","aa") → false

isMatch("aa", "*") → true
 isMatch("aa", "a*") → true

isMatch("ab", "?*") → true
 isMatch("aab", "c*a*b") → false

難度: Hard

題目給出一個(gè)字符串和一個(gè)pattern, 要求我們給出這個(gè)字符串是否匹配這個(gè)pattern. 其中通配符跟我們平常見到的一樣, 是 ? 和 * . ?代表任意單個(gè)字符, * 代表一個(gè)或多個(gè)字符.
這個(gè)題跟Leetcode 10 簡(jiǎn)單正則匹配比較類似, 可以跟這里面第二個(gè)解法一樣, 采取類似的動(dòng)態(tài)規(guī)劃解法, 在pattern里取中間某個(gè)確定的字符串序列, 將字符串和pattern分別切分成兩段再分別判定是否匹配.
例如, 字符串是 abc, 判定是否匹配到*b?, 我們可以抓住中間的b, 匹配到abc中的b, 將abc切分為["a","c"], 將*b?切分為 ["*","?"], 分別判定"a"和"*", 以及"c"和"?"是否匹配, 如果都匹配, 那么整個(gè)最終結(jié)果就是匹配的.
當(dāng)然, 事情有時(shí)候不會(huì)這么順利, 比如字符串出現(xiàn)多個(gè)b呢? 這時(shí)候需要嘗試, pattern中的b到底是字符串中的哪一個(gè)b.

這里提出一種新的, 無遞歸的解法. 基本思路為:

將pattern中所有連續(xù)多個(gè)*置換為單個(gè)*, 比如a**a置換為a*a

跟Leetcode 10 的解法一樣, 將pattern前后都確定的字符去跟輸入字符串前后匹配, 比如字符串a(chǎn)bc和模式a*c, 掐頭去尾變成 b和*, 這期間如果有不同可以直接返回不匹配.

剩下的是有*的部分, 比如pattern可能是*a*bb*c*. 這樣我們采取盡早匹配*之外字符的方式, 像上面那個(gè)pattern, 按順序, 盡早匹配a, bb, 和c, 如果在字符串結(jié)束之前都匹配ok, 這樣最終結(jié)果就是匹配成功的, 否則, 如果某個(gè)子串比如bb找不到, 或者還沒全部匹配完就已經(jīng)走到了字符串的末尾, 都算匹配失敗.

AC的程序最終可以超越75%的算法, 如下:

public class Solution {
    public boolean isMatch(String s, String p) {
        // replace all redundent ** to *
        if (p.length() > 0) {
            StringBuffer sb = new StringBuffer();
            sb.append(p.charAt(0));
            for (int i = 1; i < p.length(); i++) {
                if (p.charAt(i) != "*" || p.charAt(i - 1) != "*") {
                    sb.append(p.charAt(i));
                }
            }
            p = sb.toString();
        }
        if (p.length() == 1 && p.charAt(0) == "*") {
            return true;
        }

        int slen = s.length();
        int plen = p.length();
        int ps = 0;
        int pp = 0;
        // trim left non-star element of s and p
        // "aabb","?*b" -> "abb","*b"
        while (pp < plen && ps < slen && p.charAt(pp) != "*") {
            if (p.charAt(pp) != "?" && p.charAt(pp) != s.charAt(ps)) {
                return false;
            }
            pp++;
            ps++;
        }
        int trimleft = pp;
        s = s.substring(trimleft);
        p = p.substring(trimleft);

        // if s and p is not empty
        // trim right non-star element of s and p
        // "abb","*b" -> "ab","*"
        if (s.length() > 0 && p.length() > 0) {
            slen = s.length();
            plen = p.length();
            ps = slen - 1;
            pp = plen - 1;
            while (pp >= 0 && ps >= 0 && p.charAt(pp) != "*") {
                if (p.charAt(pp) != "?" && p.charAt(pp) != s.charAt(ps)) {
                    return false;
                }
                pp--;
                ps--;
            }
            int trimright = plen - 1 - pp;
            s = s.substring(0, slen - trimright);
            p = p.substring(0, plen - trimright);
        }
        slen = s.length();
        plen = p.length();
        // length of s or length of p is zero judgement
        if (plen == 0) {
            if (slen > 0) {
                return false;
            } else {
                return true;
            }
        }
        if (slen == 0 && (plen > 1 || plen == 1 && p.charAt(0) != "*")) {
            return false;
        }
        ps = 0;
        pp = 0;
        int ptnl = 1;
        int ptnr = 1;
        int psl = 0;
        int psr = 0;
        // first and last character of p is star
        // p: *aa*bb* -> (aa,bb)
        // locate each of the non-star sub-patterns in s sequentially
        // if all satisfies, return true
        // otherwise false
        while (ptnl < plen && ptnr < plen) {
            // ptnl and ptnr designates left and right index of current
            // sub-pattern
            // find a sub-pattern
            while (p.charAt(ptnr) != "*") {
                ptnr++;
            }
            // find match in s
            for (int i = psl; i <= slen - (ptnr - ptnl); i++) {
                int j = ptnl;
                for (; j < ptnr; j++) {
                    if (s.charAt(i + (j - ptnl)) != p.charAt(j) && p.charAt(j) != "?") {
                        break;
                    }
                }
                if (j == ptnr) {
                    // matches current sub-pattern
                    psl = i;
                    psr = psl + (ptnr - ptnl);
                    break;
                }
            }
            if (psl == psr) {
                // no match for current sub-pattern
                return false;
            }
            // go to next position for next sub-pattern
            psl = psr;
            ptnr++;
            ptnl = ptnr;
        }
        return true;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.isMatch("bb", "?*?"));
        System.out.println(s.isMatch("b", "?*?"));
        System.out.println(s.isMatch("aa", "a"));
        System.out.println(s.isMatch("aa", "aa"));
        System.out.println(s.isMatch("aaa", "aa"));
        System.out.println(s.isMatch("aa", "*"));
        System.out.println(s.isMatch("aa", "a*"));
        System.out.println(s.isMatch("ab", "?*"));
        System.out.println(s.isMatch("aab", "c*a*b"));
        System.out.println(s.isMatch("aabbaab", "a*b"));
        System.out.println(s.isMatch("aabbbaaab", "a*b*b"));
        System.out.println(s.isMatch("aaabababaaabaababbbaaaabbbbbbabbbbabbbabbaabbababab", "*ab***ba**b*b*aaab*b"));
        System.out.println(s.isMatch("aaabaaaabbbbbbaaabbabbbbababbbaaabbabbabb", "*b*bbb*baa*bba*b*bb*b*a*aab*a*"));
        System.out.println(s.isMatch(
                "abbaabbbbababaababababbabbbaaaabbbbaaabbbabaabbbbbabbbbabbabbaaabaaaabbbbbbaaabbabbbbababbbaaabbabbabb",
                "***b**a*a*b***b*a*b*bbb**baa*bba**b**bb***b*a*aab*a**"));

        System.out.println(s.isMatch("bbbbbbbabbaabbabbbbaaabbabbabaaabbababbbabbbabaaabaab", "b*b*ab**ba*b**b***bba"));
        System.out.println(s.isMatch(
                "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"));
    }
}

main中包含一部分測(cè)試用例.

這里, 我突然發(fā)現(xiàn), 上面第一步, 將pattern中所有連續(xù)多個(gè)*置換為單個(gè)*, 雖然可以讓pattern變得更簡(jiǎn)單, 但其實(shí)不是非常必要, 既然后面使用游標(biāo), 就可以略過連續(xù)多個(gè)的*. 比如上面接近最后有一句ptnr++, 實(shí)際上就是略過了其后的一個(gè)*, int ptnr=1; 就是略過了開頭的一個(gè)*. 把這些都置換為略過連續(xù)的*, 即可. 改進(jìn)后的程序如下:

public class Solution2 {
    public boolean isMatch(String s, String p) {
        int slen = s.length();
        int plen = p.length();
        int ps = 0;
        int pp = 0;

        // trim left non-star element of s and p
        // "aabb","?*b" -> "abb","*b"
        while (pp < plen && ps < slen && p.charAt(pp) != "*") {
            if (p.charAt(pp) != "?" && p.charAt(pp) != s.charAt(ps)) {
                return false;
            }
            pp++;
            ps++;
        }
        int trimleft = pp;
        s = s.substring(trimleft);
        p = p.substring(trimleft);

        // if s and p is not empty
        // trim right non-star element of s and p
        // "abb","*b" -> "ab","*"
        slen = s.length();
        plen = p.length();
        if (slen > 0 && plen > 0) {
            ps = slen - 1;
            pp = plen - 1;
            while (pp >= 0 && ps >= 0 && p.charAt(pp) != "*") {
                if (p.charAt(pp) != "?" && p.charAt(pp) != s.charAt(ps)) {
                    return false;
                }
                pp--;
                ps--;
            }
            int trimright = plen - 1 - pp;
            s = s.substring(0, slen - trimright);
            p = p.substring(0, plen - trimright);
        }
        slen = s.length();
        plen = p.length();
        // length of s or length of p is zero judgement
        if (plen == 0) {
            if (slen > 0) {
                return false;
            } else {
                return true;
            }
        }
        
        ps = 0;
        pp = 0;
        int ptnl = 0;
        int ptnr = 0;
        int psl = 0;
        int psr = 0;
        // skip preceding *
        while (ptnr < plen && p.charAt(ptnr) == "*") {
            ptnr++;
        }
        ptnl = ptnr;
        // first and last character of p is star
        // p: *aa*bb* -> (aa,bb)
        // locate each of the non-star sub-patterns in s sequentially
        // if all satisfies, return true
        // otherwise false
        while (ptnl < plen && ptnr < plen) {
            // ptnl and ptnr designates left and right index of current
            // sub-pattern
            // find a sub-pattern
            while (ptnr < plen && p.charAt(ptnr) != "*") {
                ptnr++;
            }
            // find match in s
            for (int i = psl; i <= slen - (ptnr - ptnl); i++) {
                int j = ptnl;
                for (; j < ptnr; j++) {
                    if (s.charAt(i + (j - ptnl)) != p.charAt(j) && p.charAt(j) != "?") {
                        break;
                    }
                }
                if (j == ptnr) {
                    // matches current sub-pattern
                    psl = i;
                    psr = psl + (ptnr - ptnl);
                    break;
                }
            }
            if (psl == psr) {
                // no match for current sub-pattern
                return false;
            }
            // go to next position for next sub-pattern
            psl = psr;
            while (ptnr < plen && p.charAt(ptnr) == "*") {
                ptnr++;
            }
            ptnl = ptnr;
        }
        return true;
    }
}

最終提交結(jié)果速度又快了很多, 在99.49%的提交之前: