Wildcard Matching@leetcode

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

Have you been asked this question in an interview?

This problem can be viewed as a simplified parser problem. It's like a pre-scanner to exam whether the sentences are correct in grammar. 

The hard part here is '*'. Once we meet a '*' in P, it means we may have difference ways to match the rest subarray. So we use two pointers star and ss to store the position information of both p and s, when we have a '*'. Pay attention that we should declare const char * star, ss, because p and s are const but not variables. Also, the way to judge the end of a char *p array is !*p and p != '0/', but string 

1. if *p == '?' || *p == *s  

       p ++, s++, continue

2.  if *p == '*', then we set star = p++, ss = s, continue;

3. if(star) then we do p = star + 1, s = ++ss, continue;

4. return false;

The key point is to backtrack the position of p and s when we meet a '*' here. The logic is once 1,2 situations are not met, it means it's not work out here. So we need to backtrack, now we go to 3, if there is a '*' before, thus star is not empty. Then we set p = star + 1, s = ++ss. We need to pay attention here is that, we only change the position of p and s, ss but not star, thus if this way does not work out neither. we can backtrack again.