【解题报告】【lintcode192】Wildcard Matching

题意

判断两个可能包含通配符“？”和“”的字符串是否匹配。匹配规则如下： '?' 可以匹配任何单个字符。 '' 可以匹配任意字符串（包括空字符串）。 两个串完全匹配才算匹配成功。 一些例子： isMatch("aa","a") → false isMatch("aa","aa") → true isMatch("aaa","aa") → false isMatch("aa", "") → true isMatch("aa", "a") → true isMatch("ab", "?") → true isMatch("aab", "ca*b") → false

解答

对于'?'的匹配很简单，直接忽略即可 对于''的匹配，找到这个符号时，记录它的位置和匹配串的位置，在下一次开始时从这个点后开始匹配，如果不匹配就在匹配串上面往后移一位 以上过程结束后，对于匹配串的遍历就结束了，如果模式串还有未遍历的部分，只能是

代码

 public boolean isMatch(String str, String pattern){
        int s = 0;
        int p = 0;
        int starIndex = -1;
        int match = 0;
        while (s < str.length()){
            if (p<pattern.length()&&(pattern.charAt(p) == '?'||pattern.charAt(p) == str.charAt(s))){
                p++;
                s++;
            }else if(p < pattern.length()&&pattern.charAt(p) == '*'){
                starIndex = p;
                p++;
                match = s;
            }else if(starIndex != -1){
                match++;
                s = match;
                p = starIndex+1;
            }else{
                return false;
            }
        }
        while (p<pattern.length()&&pattern.charAt(p) == '*')
            p++;
       return p == pattern.length();
    }