Wildcard Matching

WildcardMatching.java

/**
 * 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
 */
public class Solution {
    public boolean isMatch(String s, String p) {
        int len_s = s.length();
        int len_p = p.length();
        if(len_s == 0 && len_p == 0) 
            return true;
        int i = 0, j = 0;
        // save the last matched index
        int start_s = -1, start_p = -1;
        while (i < len_s) {
            if (j < len_p && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?')) {
                i++;
                j++;
            } else if (j < len_p && p.charAt(j) == '*') {
                while(j < len_p && p.charAt(j) == '*') 
                    j++;
                if(j == len_p)
                    return true;
                // 置上一个开始比较的位置
                start_p = j;
                start_s = i;
            } else if ((j >= len_p || s.charAt(i) != p.charAt(j)) && start_p > -1) {
                start_s++;
                // 恢复到上一次比较的下一个位置
                j = start_p;
                i = start_s;
            } else {
                return false;
            }
        }
        while (j < len_p) {
            if (p.charAt(j) != '*')
                return false;
            j++;
        }
        return true;
    }
}