1+ /*
2+ Author: King, wangjingui@outlook.com
3+ Date: Dec 20, 2014
4+ Problem: Wildcard Matching
5+ Difficulty: Medium
6+ Source: https://oj.leetcode.com/problems/wildcard-matching/
7+ Notes:
8+ Implement wildcard pattern matching with support for '?' and '*'.
9+ '?' Matches any single character.
10+ '*' Matches any sequence of characters (including the empty sequence).
11+ The matching should cover the entire input string (not partial).
12+ The function prototype should be:
13+ bool isMatch(const char *s, const char *p)
14+ Some examples:
15+ isMatch("aa","a") ? false
16+ isMatch("aa","aa") ? true
17+ isMatch("aaa","aa") ? false
18+ isMatch("aa", "*") ? true
19+ isMatch("aa", "a*") ? true
20+ isMatch("ab", "?*") ? true
21+ isMatch("aab", "c*a*b") ? false
22+
23+ Solution: 1. if s[i] == p[j] || p[j] == '?', ++i and ++j.
24+ ii, jj, record the positon of '*' in s and p, ++j and go on.
25+ if not match, go back to star, i = ++ii;
26+ */
27+
28+ public class Solution {
29+ public boolean isMatch (String s ,String p ) {
30+ int ii = -1 ,jj = -1 ,i =0 ,j =0 ;
31+ while (i <s .length ()) {
32+ if (j <p .length () &&p .charAt (j ) =='*' ) {
33+ while (j <p .length () &&p .charAt (j ) =='*' ) ++j ;
34+ if (j ==p .length ())return true ;
35+ ii =i ;
36+ jj =j ;
37+ }
38+ if (j <p .length () && (p .charAt (j ) =='?' ||p .charAt (j ) ==s .charAt (i ))) {
39+ ++i ; ++j ;
40+ }else {
41+ if (ii == -1 )return false ;
42+ ++ii ;
43+ i =ii ;
44+ j =jj ;
45+ }
46+ }
47+ while (j <p .length () &&p .charAt (j ) =='*' ) ++j ;
48+ return i ==s .length () &&j ==p .length ();
49+ }
50+ }
