[LeetCode] 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

 解题思路：
1. 最开始想到的就是递归，但通不过大数据。
2. 后来又想到用数组，类似edit distance的dp。 如果 p(j) == '*', 则match[i][j] = match[i][j-1] || match[i-1][j]. 当p(j) == '?' or p(j) = s(i) 则，match[i][j] = match[i-1][j-1]. 但这样会需要很大的额外空间并且又多了很多不必要的计算。
3. 就是将解法1递归添加一个stack来存储 ＊和当前s的位置。但是同样通不过大数据，所以我们要进行进一步分析，进行剪枝优化
    3.1 首先想到的就是当多个*连续出现时，它等同于一个*
    3.2 每次回溯时，我们仅需要回溯到最近的一个*的相关位置，对之前出现的*, 我们可以舍弃.
   比如，s="accbcbccx", p="a*b*d",  "a*b" 可以与"accb" 或者 "accbcb" 匹配，当我们发现"cbccx"不能与"*d"匹配时，我们也不回溯到 "accbcb" 然后 匹配 "ccx" 与"*b"
因为第二个*可以匹配任何的字符。

Java Code:

 public boolean isMatch(String s, String p) {
        int s0 = 0;
        int p0 = 0;
        int pre_p = -1, pre_s = -1;
       
       while(s0 < s.length()){
           if(s0 < s.length() && p0 < p.length() && (s.charAt(s0) == p.charAt(p0) || p.charAt(p0) == '?')){
               s0++;
               p0++;
           }else if(p0 < p.length() && p.charAt(p0) == '*'){
               while(p0 < p.length() && p.charAt(p0) == '*') p0++;
               if(p0 == p.length()) return true;
               
               pre_p = p0;
               pre_s = s0;
           }else if(pre_p > -1){
               pre_s++;
               s0 = pre_s;
               p0 = pre_p;
           }else{
               return false;
           }    
       }
       
       while(p0 < p.length() && p.charAt(p0) == '*') p0++;
       
      return p0 == p.length();
    }