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

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

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

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

將pattern中所有連續多個*置換為單個*, 比如a**a置換為a*a

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

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

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中包含一部分測試用例.

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

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

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