# 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();
``````