public class WildcardMatching {
    /**
     * 失效回溯法
     *
     * 思想1：對于通配符匹配方案，我們主要的難點問題是在于通配符*的匹配，
     *          所以首要問題我們要定位到*所在的位置，定位到*之后我們再在此處做文章
     * 思想2：單值通配符？姑且忽略，我們只要把他當(dāng)作任意字符處理即可，讓他等價于任意字符。
     * 思想3：假設(shè)目標(biāo)串和模板串都是普通字符串，不含有任何通配符，那么此時我們的比較方式應(yīng)該是逐個字符的比較方式
     * 思想4：假設(shè)另一種特殊情況，我們的模板串是目標(biāo)串中間穿插的通配符，此時我們在處理的過程中可以跳過通配符
     * 思想5：在思想4的基礎(chǔ)上我們引申一下，我們思考一下我們應(yīng)該如何跳過通配符，如果只是單純的忽略，對我們解決問題沒有任何意義，
     *          假設(shè)我們模板串中只有一個通配符，當(dāng)前前面的若干字符匹配成功，此時遇見通配符，此時
     *          比較目標(biāo)串當(dāng)前索引開始的子串與模板串當(dāng)前通配符之后的子串。如果子串能夠匹配，那么自然而然的忽略了通配符
     * 思想6：在思想5的基礎(chǔ)上我們繼續(xù)引申，如果子串匹配失效，能夠證明此時的匹配完全失效嗎？
     *          不能，因為我們通配符之后的子串可以只匹配目標(biāo)串的最后幾位，我們的通配符可以代替中間的所有字符。
     *          那么問題來了，我們接下來該怎么辦？
     * 思想7：在思想6的基礎(chǔ)上我們繼續(xù)引申，假設(shè)我們模板串的通配符兩端能夠與目標(biāo)串的首尾匹配，那么我們該如何解決中間的內(nèi)容匹配呢？
     *          我們再回想一下思想5中忽略通配符的過程，因為我們通配符就是用來忽略字符的，我們?yōu)槭裁匆雎运兀?     *          問題出在了我們思想4中的假設(shè)，因為我們假設(shè)的是通配符是多余的，但是仔細(xì)想一下，
     *          其實通配符多余只是一種通配符匹配到0個字符的情況，那么通配符如果匹配多個字符該如何操作呢，
     *          此時，我們是不是應(yīng)該忽略目標(biāo)串中的字符，那么怎么忽略呢？我們再想一想思想5中的子串比較，
     *          我們是不是可以通過縮短目標(biāo)串的子串來達到忽略的效果呢？可以達到，那么問題又來了，怎么縮短呢？
     * 思想8：在思想7的基礎(chǔ)上我們再思考，假設(shè)兩個子串匹配失效之后，我們怎么能夠回到起點進行忽略操作？
     *          我們是不是就應(yīng)該對目標(biāo)子串的起始位置進行記錄呢，這樣匹配失敗后我能夠回到最初的起點。
     *          于是目標(biāo)子串回到起點后加1后便達到了忽略一個字符的效果。但是目標(biāo)子串忽略一個字符表示這個字符是被通配符抵消掉的，
     *          那接下來的目標(biāo)子串應(yīng)該是與模板串的哪部分比較呢，是不是也應(yīng)該是通配符后邊的子串。
     *          那么我們同樣需要對通配符的位置進行記錄。我們可以將這兩個標(biāo)記稱為回溯點。
     * 思想9：在思想8的回溯思路上，我們凡是遇到失效，就回溯到回溯點的位置，直到目標(biāo)串處理完畢
     * 思想10：目標(biāo)串匹配結(jié)束后，已經(jīng)確定目標(biāo)串滿足我們模板串，此時需要檢測模板串是否滿足目標(biāo)串，
     *          也就是說模板串是否還有殘余串，如果殘余串是*放行，否則阻斷。
     *          當(dāng)殘余串檢測完畢之后，此時如果模板串檢測到的索引剛好等于模板串的索引，表示模板串滿足目標(biāo)串。
     *          到此，我們整個問題的解決思路已經(jīng)明確。
     * 思想11：前面的思想我們都是基于單個通配符的基礎(chǔ)上進行引申的，那么多個通配符又能否滿足呢？仔細(xì)思考一下。是完全可以，
     *          因為如果能夠匹配到下一個通配符的位置，那么下一個通配符將會接替前一個通配符的監(jiān)聽，前一個通配符的職責(zé)已經(jīng)完成。
     * 思想12：在思想2中我們忽略的單值通配符應(yīng)該如何處理呢，我們前文說過，讓他等價于任何字符，也就是說，
     *          在我們判斷目標(biāo)串中某個字符和模板串中的某個字符是否相等時，如果模板串中的字符是單值通配符，直接按照匹配成功，放行即可。
     *          至此，所有的疑點都已經(jīng)一一擊破，真相已經(jīng)水落石出。
     * @param s 待匹配字符串
     * @param p 通配符模板字符串
     * @return 匹配結(jié)果
     */
    boolean isMatch(String s, String p) {
        // i 用來記錄s串檢測的索引的位置
        int i = 0;
        // j 用來記錄p串檢測的索引的位置
        int j = 0;
        // 記錄 待測串i的回溯點
        int ii = -1;
        // 記錄 通配符*的回溯點
        int jj = -1;

        // 以s字符串的長度為循環(huán)基數(shù)，用i來記錄s串當(dāng)前的位置
        while (i < s.length()) {
            // 用j來記錄p串的當(dāng)前位置，檢測p串中j位置的值是不是通配符*
            if (j < p.length() && p.charAt(j) == '*') {
                // 如果在p串中碰到通配符*，復(fù)制兩串的當(dāng)前索引，記錄當(dāng)前的位置，并對p串+1，定位到非通配符位置
                ii = i;
                jj = j;
                j++;
            }
            else if (j < p.length() // 檢測p串是否結(jié)束
                    && (s.charAt(i) == p.charAt(j)   // 檢測兩串當(dāng)前位置的值是否相等
                    || p.charAt(j) == '?')) { // 檢測p串中j位置是否是單值通配符？
                // 如果此時p串還在有效位置上，那么兩串當(dāng)前位置相等或者p串中是單值通配符，表明此時匹配通過，兩串均向前移動一步
                i++;
                j++;
            }
            else {
                // 如果在以上兩種情況下均放行，表明此次匹配是失敗的，那么此時就要明確一點，s串是否在被p串中的通配符*監(jiān)聽著，
                // 因為在首次判斷中如果碰到通配符*，我們會將他當(dāng)前索引的位置記錄在jj的位置上，
                // 如果jj = -1 表明匹配失敗，當(dāng)前s串不在監(jiān)聽位置上
                if (jj == -1) return false;
                // 如果此時在s串在通配符*的監(jiān)聽下， 讓p串回到通配符*的位置上繼續(xù)監(jiān)聽下一個字符
                j = jj;
                // 讓i回到s串中與通配符對應(yīng)的當(dāng)前字符的下一個字符上，也就是此輪匹配只放行一個字符
                i = ii + 1;
            }
        }

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

        // 此時查看p是否已經(jīng)檢測到最后，如果檢測到最后表示匹配成功，否則匹配失敗
        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));
    }
}