Java实现通配符匹配

public class WildcardMatching {
    /**
     * 失效回溯法
     *
     * 思想1：对于通配符匹配方案，我们主要的难点问题是在于通配符*的匹配，
     *          所以首要问题我们要定位到*所在的位置，定位到*之后我们再在此处做文章
     * 思想2：单值通配符？姑且忽略，我们只要把他当作任意字符处理即可，让他等价于任意字符。
     * 思想3：假设目标串和模板串都是普通字符串，不含有任何通配符，那么此时我们的比较方式应该是逐个字符的比较方式
     * 思想4：假设另一种特殊情况，我们的模板串是目标串中间穿插的通配符，此时我们在处理的过程中可以跳过通配符
     * 思想5：在思想4的基础上我们引申一下，我们思考一下我们应该如何跳过通配符，如果只是单纯的忽略，对我们解决问题没有任何意义，
     *          假设我们模板串中只有一个通配符，当前前面的若干字符匹配成功，此时遇见通配符，此时
     *          比较目标串当前索引开始的子串与模板串当前通配符之后的子串。如果子串能够匹配，那么自然而然的忽略了通配符
     * 思想6：在思想5的基础上我们继续引申，如果子串匹配失效，能够证明此时的匹配完全失效吗？
     *          不能，因为我们通配符之后的子串可以只匹配目标串的最后几位，我们的通配符可以代替中间的所有字符。
     *          那么问题来了，我们接下来该怎么办？
     * 思想7：在思想6的基础上我们继续引申，假设我们模板串的通配符两端能够与目标串的首尾匹配，那么我们该如何解决中间的内容匹配呢？
     *          我们再回想一下思想5中忽略通配符的过程，因为我们通配符就是用来忽略字符的，我们为什么要忽略他呢，
     *          问题出在了我们思想4中的假设，因为我们假设的是通配符是多余的，但是仔细想一下，
     *          其实通配符多余只是一种通配符匹配到0个字符的情况，那么通配符如果匹配多个字符该如何操作呢，
     *          此时，我们是不是应该忽略目标串中的字符，那么怎么忽略呢？我们再想一想思想5中的子串比较，
     *          我们是不是可以通过缩短目标串的子串来达到忽略的效果呢？可以达到，那么问题又来了，怎么缩短呢？
     * 思想8：在思想7的基础上我们再思考，假设两个子串匹配失效之后，我们怎么能够回到起点进行忽略操作？
     *          我们是不是就应该对目标子串的起始位置进行记录呢，这样匹配失败后我能够回到最初的起点。
     *          于是目标子串回到起点后加1后便达到了忽略一个字符的效果。但是目标子串忽略一个字符表示这个字符是被通配符抵消掉的，
     *          那接下来的目标子串应该是与模板串的哪部分比较呢，是不是也应该是通配符后边的子串。
     *          那么我们同样需要对通配符的位置进行记录。我们可以将这两个标记称为回溯点。
     * 思想9：在思想8的回溯思路上，我们凡是遇到失效，就回溯到回溯点的位置，直到目标串处理完毕
     * 思想10：目标串匹配结束后，已经确定目标串满足我们模板串，此时需要检测模板串是否满足目标串，
     *          也就是说模板串是否还有残余串，如果残余串是*放行，否则阻断。
     *          当残余串检测完毕之后，此时如果模板串检测到的索引刚好等于模板串的索引，表示模板串满足目标串。
     *          到此，我们整个问题的解决思路已经明确。
     * 思想11：前面的思想我们都是基于单个通配符的基础上进行引申的，那么多个通配符又能否满足呢？仔细思考一下。是完全可以，
     *          因为如果能够匹配到下一个通配符的位置，那么下一个通配符将会接替前一个通配符的监听，前一个通配符的职责已经完成。
     * 思想12：在思想2中我们忽略的单值通配符应该如何处理呢，我们前文说过，让他等价于任何字符，也就是说，
     *          在我们判断目标串中某个字符和模板串中的某个字符是否相等时，如果模板串中的字符是单值通配符，直接按照匹配成功，放行即可。
     *          至此，所有的疑点都已经一一击破，真相已经水落石出。
     * @param s 待匹配字符串
     * @param p 通配符模板字符串
     * @return 匹配结果
     */
    boolean isMatch(String s, String p) {
        // i 用来记录s串检测的索引的位置
        int i = 0;
        // j 用来记录p串检测的索引的位置
        int j = 0;
        // 记录 待测串i的回溯点
        int ii = -1;
        // 记录 通配符*的回溯点
        int jj = -1;

        // 以s字符串的长度为循环基数，用i来记录s串当前的位置
        while (i < s.length()) {
            // 用j来记录p串的当前位置，检测p串中j位置的值是不是通配符*
            if (j < p.length() && p.charAt(j) == '*') {
                // 如果在p串中碰到通配符*，复制两串的当前索引，记录当前的位置，并对p串+1，定位到非通配符位置
                ii = i;
                jj = j;
                j++;
            }
            else if (j < p.length() // 检测p串是否结束
                    && (s.charAt(i) == p.charAt(j)   // 检测两串当前位置的值是否相等
                    || p.charAt(j) == '?')) { // 检测p串中j位置是否是单值通配符？
                // 如果此时p串还在有效位置上，那么两串当前位置相等或者p串中是单值通配符，表明此时匹配通过，两串均向前移动一步
                i++;
                j++;
            }
            else {
                // 如果在以上两种情况下均放行，表明此次匹配是失败的，那么此时就要明确一点，s串是否在被p串中的通配符*监听着，
                // 因为在首次判断中如果碰到通配符*，我们会将他当前索引的位置记录在jj的位置上，
                // 如果jj = -1 表明匹配失败，当前s串不在监听位置上
                if (jj == -1) return false;
                // 如果此时在s串在通配符*的监听下， 让p串回到通配符*的位置上继续监听下一个字符
                j = jj;
                // 让i回到s串中与通配符对应的当前字符的下一个字符上，也就是此轮匹配只放行一个字符
                i = ii + 1;
            }
        }

        // 当s串中的每一个字符都与p串中的字符进行匹配之后，对p串的残余串进行检查，如果残余串是一个*那么继续检测，否则跳出
        while (j < p.length() && p.charAt(j) == '*') j++;

        // 此时查看p是否已经检测到最后，如果检测到最后表示匹配成功，否则匹配失败
        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));
    }
}