public class WildcardMatching {
    /**
     * 失效回溯法
     *
     * 思想1：對(duì)于通配符匹配方案辣吃，我們主要的難點(diǎn)問(wèn)題是在于通配符*的匹配，
     *          所以首要問(wèn)題我們要定位到*所在的位置，定位到*之后我們?cè)僭诖颂幾鑫恼?     * 思想2：?jiǎn)沃低ㄅ浞抗们液雎裕覀冎灰阉?dāng)作任意字符處理即可炊琉，讓他等價(jià)于任意字符。
     * 思想3：假設(shè)目標(biāo)串和模板串都是普通字符串，不含有任何通配符稼稿，那么此時(shí)我們的比較方式應(yīng)該是逐個(gè)字符的比較方式
     * 思想4：假設(shè)另一種特殊情況，我們的模板串是目標(biāo)串中間穿插的通配符讳窟，此時(shí)我們?cè)谔幚淼倪^(guò)程中可以跳過(guò)通配符
     * 思想5：在思想4的基礎(chǔ)上我們引申一下让歼，我們思考一下我們應(yīng)該如何跳過(guò)通配符，如果只是單純的忽略丽啡，對(duì)我們解決問(wèn)題沒(méi)有任何意義谋右，
     *          假設(shè)我們模板串中只有一個(gè)通配符，當(dāng)前前面的若干字符匹配成功补箍，此時(shí)遇見(jiàn)通配符改执，此時(shí)
     *          比較目標(biāo)串當(dāng)前索引開(kāi)始的子串與模板串當(dāng)前通配符之后的子串。如果子串能夠匹配坑雅，那么自然而然的忽略了通配符
     * 思想6：在思想5的基礎(chǔ)上我們繼續(xù)引申辈挂，如果子串匹配失效，能夠證明此時(shí)的匹配完全失效嗎裹粤？
     *          不能终蒂，因?yàn)槲覀兺ㄅ浞蟮淖哟梢灾黄ヅ淠繕?biāo)串的最后幾位，我們的通配符可以代替中間的所有字符遥诉。
     *          那么問(wèn)題來(lái)了拇泣，我們接下來(lái)該怎么辦？
     * 思想7：在思想6的基礎(chǔ)上我們繼續(xù)引申矮锈，假設(shè)我們模板串的通配符兩端能夠與目標(biāo)串的首尾匹配霉翔，那么我們?cè)撊绾谓鉀Q中間的內(nèi)容匹配呢？
     *          我們?cè)倩叵胍幌滤枷?中忽略通配符的過(guò)程苞笨，因?yàn)槲覀兺ㄅ浞褪怯脕?lái)忽略字符的债朵，我們?yōu)槭裁匆雎运兀?     *          問(wèn)題出在了我們思想4中的假設(shè)，因?yàn)槲覀兗僭O(shè)的是通配符是多余的猫缭，但是仔細(xì)想一下葱弟，
     *          其實(shí)通配符多余只是一種通配符匹配到0個(gè)字符的情況，那么通配符如果匹配多個(gè)字符該如何操作呢猜丹，
     *          此時(shí)芝加，我們是不是應(yīng)該忽略目標(biāo)串中的字符，那么怎么忽略呢？我們?cè)傧胍幌胨枷?中的子串比較藏杖，
     *          我們是不是可以通過(guò)縮短目標(biāo)串的子串來(lái)達(dá)到忽略的效果呢将塑？可以達(dá)到，那么問(wèn)題又來(lái)了蝌麸，怎么縮短呢点寥？
     * 思想8：在思想7的基礎(chǔ)上我們?cè)偎伎迹僭O(shè)兩個(gè)子串匹配失效之后来吩，我們?cè)趺茨軌蚧氐狡瘘c(diǎn)進(jìn)行忽略操作敢辩？
     *          我們是不是就應(yīng)該對(duì)目標(biāo)子串的起始位置進(jìn)行記錄呢，這樣匹配失敗后我能夠回到最初的起點(diǎn)弟疆。
     *          于是目標(biāo)子串回到起點(diǎn)后加1后便達(dá)到了忽略一個(gè)字符的效果戚长。但是目標(biāo)子串忽略一個(gè)字符表示這個(gè)字符是被通配符抵消掉的，
     *          那接下來(lái)的目標(biāo)子串應(yīng)該是與模板串的哪部分比較呢怠苔，是不是也應(yīng)該是通配符后邊的子串同廉。
     *          那么我們同樣需要對(duì)通配符的位置進(jìn)行記錄。我們可以將這兩個(gè)標(biāo)記稱(chēng)為回溯點(diǎn)柑司。
     * 思想9：在思想8的回溯思路上迫肖，我們凡是遇到失效，就回溯到回溯點(diǎn)的位置攒驰，直到目標(biāo)串處理完畢
     * 思想10：目標(biāo)串匹配結(jié)束后蟆湖，已經(jīng)確定目標(biāo)串滿(mǎn)足我們模板串，此時(shí)需要檢測(cè)模板串是否滿(mǎn)足目標(biāo)串讼育，
     *          也就是說(shuō)模板串是否還有殘余串帐姻，如果殘余串是*放行，否則阻斷奶段。
     *          當(dāng)殘余串檢測(cè)完畢之后，此時(shí)如果模板串檢測(cè)到的索引剛好等于模板串的索引剥纷，表示模板串滿(mǎn)足目標(biāo)串痹籍。
     *          到此，我們整個(gè)問(wèn)題的解決思路已經(jīng)明確晦鞋。
     * 思想11：前面的思想我們都是基于單個(gè)通配符的基礎(chǔ)上進(jìn)行引申的蹲缠，那么多個(gè)通配符又能否滿(mǎn)足呢？仔細(xì)思考一下悠垛。是完全可以线定，
     *          因?yàn)槿绻軌蚱ヅ涞较乱粋€(gè)通配符的位置，那么下一個(gè)通配符將會(huì)接替前一個(gè)通配符的監(jiān)聽(tīng)确买，前一個(gè)通配符的職責(zé)已經(jīng)完成斤讥。
     * 思想12：在思想2中我們忽略的單值通配符應(yīng)該如何處理呢，我們前文說(shuō)過(guò)湾趾，讓他等價(jià)于任何字符芭商，也就是說(shuō)派草，
     *          在我們判斷目標(biāo)串中某個(gè)字符和模板串中的某個(gè)字符是否相等時(shí)，如果模板串中的字符是單值通配符铛楣，直接按照匹配成功近迁，放行即可。
     *          至此簸州，所有的疑點(diǎn)都已經(jīng)一一擊破鉴竭，真相已經(jīng)水落石出。
     * @param s 待匹配字符串
     * @param p 通配符模板字符串
     * @return 匹配結(jié)果
     */
    boolean isMatch(String s, String p) {
        // i 用來(lái)記錄s串檢測(cè)的索引的位置
        int i = 0;
        // j 用來(lái)記錄p串檢測(cè)的索引的位置
        int j = 0;
        // 記錄 待測(cè)串i的回溯點(diǎn)
        int ii = -1;
        // 記錄 通配符*的回溯點(diǎn)
        int jj = -1;

        // 以s字符串的長(zhǎng)度為循環(huán)基數(shù)岸浑，用i來(lái)記錄s串當(dāng)前的位置
        while (i < s.length()) {
            // 用j來(lái)記錄p串的當(dāng)前位置搏存，檢測(cè)p串中j位置的值是不是通配符*
            if (j < p.length() && p.charAt(j) == '*') {
                // 如果在p串中碰到通配符*，復(fù)制兩串的當(dāng)前索引助琐，記錄當(dāng)前的位置祭埂，并對(duì)p串+1，定位到非通配符位置
                ii = i;
                jj = j;
                j++;
            }
            else if (j < p.length() // 檢測(cè)p串是否結(jié)束
                    && (s.charAt(i) == p.charAt(j)   // 檢測(cè)兩串當(dāng)前位置的值是否相等
                    || p.charAt(j) == '?')) { // 檢測(cè)p串中j位置是否是單值通配符兵钮？
                // 如果此時(shí)p串還在有效位置上蛆橡，那么兩串當(dāng)前位置相等或者p串中是單值通配符，表明此時(shí)匹配通過(guò)掘譬，兩串均向前移動(dòng)一步
                i++;
                j++;
            }
            else {
                // 如果在以上兩種情況下均放行泰演，表明此次匹配是失敗的，那么此時(shí)就要明確一點(diǎn)葱轩，s串是否在被p串中的通配符*監(jiān)聽(tīng)著睦焕，
                // 因?yàn)樵谑状闻袛嘀腥绻龅酵ㄅ浞?，我們會(huì)將他當(dāng)前索引的位置記錄在jj的位置上靴拱，
                // 如果jj = -1 表明匹配失敗垃喊，當(dāng)前s串不在監(jiān)聽(tīng)位置上
                if (jj == -1) return false;
                // 如果此時(shí)在s串在通配符*的監(jiān)聽(tīng)下， 讓p串回到通配符*的位置上繼續(xù)監(jiān)聽(tīng)下一個(gè)字符
                j = jj;
                // 讓i回到s串中與通配符對(duì)應(yīng)的當(dāng)前字符的下一個(gè)字符上袜炕，也就是此輪匹配只放行一個(gè)字符
                i = ii + 1;
            }
        }

        // 當(dāng)s串中的每一個(gè)字符都與p串中的字符進(jìn)行匹配之后本谜，對(duì)p串的殘余串進(jìn)行檢查，如果殘余串是一個(gè)*那么繼續(xù)檢測(cè)偎窘，否則跳出
        while (j < p.length() && p.charAt(j) == '*') j++;

        // 此時(shí)查看p是否已經(jīng)檢測(cè)到最后乌助，如果檢測(cè)到最后表示匹配成功，否則匹配失敗
        return j == p.length();
    }

    public static void main(String args[]) {
        String s = "aabdsfgbcde";
        String p = "aa*bcde";

        WildcardMatching wcm = new WildcardMatching();
        System.out.println(wcm.isMatch(s, p));
    }
}