Wildcard Matching

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

Tips:

O(n)

two pointer，两个字串对应两个指针。i， j 如果能匹配则index都加1。用一个starIndex来储存曾遇到过得star的位置，初始为-1，遇到star就赋值starindex，也用iIndex记住此时i的位置。遇到不能匹配时，如果starindex不等于-1说明遇到过star。则重置ij到iindex+ 1和starindex + 1，iindex++意思是把这一位i匹配到记录中的star里去。

Code：

public boolean isMatch(String s, String p) {
    int i = 0;
    int j = 0;
    int starIndex = -1;
    int iIndex = -1;

    while (i < s.length()) {
        if (j < p.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
            ++i;
            ++j;
        } else if (j < p.length() && p.charAt(j) == '*') {
            starIndex = j;        
            iIndex = i;
            j++;
        } else if (starIndex != -1) {
            j = starIndex + 1;
            i = iIndex+1;
            iIndex++;
        } else {
            return false;
        }
    }

    while (j < p.length() && p.charAt(j) == '*') {
        ++j;
    }

    return j == p.length();