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

A:
1: 先用递归，估计会嫌太慢。先做出来再说吧。

 嗯，确实很慢。问题主要出在* 上。 下面是递归的解法。

public class Solution {
    public boolean isMatch(String s, String p) {
        if(s.length() ==0){
            if(p.length()==0)
                return true;
            else
                return p.charAt(0) =='*'? isMatch(s, p.substring(1)) : false;
        }
        if(p.length() ==0)
            return false;

        if(s.charAt(0) == p.charAt(0) || p.charAt(0) == '?')
            return isMatch(s.substring(1), p.substring(1));
        else if( p.charAt(0) == '*' )
            return isMatch(s,p.substring(1)) || isMatch(s.substring(1),p);
        else
            return false;
    }
}

上面这个解法，对于输入：

"babbbaabbaaaaabbababaaaabbbbbbbbbbabbaaaabbababbabaa", "**a****a**b***ab***a*bab" 

就会严重超时。

问题就出在 倒数第二个return 语句上，|| 后面那个helper（）。当s只match了一个。这样效率很低。

  Solution 2
贪心算法，只需要依据连续的’*'，将p分割成一些不带’*'的子串。然后在s中依次匹配就好了，只不过需要特殊照顾一下首尾两个子串：
1.对于开头不是’*'的p，第一个子串必须从s[0]开始匹配
2.对于结尾不是’*'的p，最后一个子串必须在s的尾巴上匹配

--------------------------确实快了很多，可是，当*后面的第一个字符串(非通配符）在s中match的次数过多的时候， 速度会显著降低。-------------------这时候，我们就不需要匹配所有的。 只需要找到匹配的即可。 嗯，如果是最后的字串，需要匹配最后的位置。
还需要继续优化。




-------------------solution 3 -----------------------
我们提出solution 3，  也就是把? 和其余的字符串放一起。
因此， p = "a???*a??b"被我们分成  [a,  ???, * ,   a??b] 四个子pattern。 这样出了第一个前面没有*外， 别的子pattern前面都有*， 可以随便移动位置。 （当然，需要自己写 字符匹配的函数。这个很简单）
 ----------------这里深入分析了8种解法----------- （还有代码）
--------------------- 这是第二遍的实现--------------思路跟solution3 一样-------只是更简洁了----

public class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null || p == null) // should not occur
            return false;
        if (s.length() == 0)
            return p.length() == 0 || (p.length() == 1 && p.charAt(0) == '*');
        if (p.length() == 0)// if run this line, s.length() != 0
            return false;
        // check the first is *
        if (p.charAt(0) != '*') {
            int firstStartIndex = p.indexOf("*");
            if (firstStartIndex < 0) { // if p does not contains *
                return s.length() == p.length() && findFirstMatch(s, p) == 0;
            } else { // / p contains *
                String partP = p.substring(0, firstStartIndex);
                int matchPos = findFirstMatch(s, partP);
                if (matchPos != 0) { // if not fint at the first place
                    return false;
                } else { // we have find match at first place
                    s = s.substring(partP.length());
                    p = p.substring(partP.length());
                }
            }
        }
        String[] patternP = p.split("\\*");
        // all patternP[i] have a * ahead
        for (int i = 0; i < patternP.length; i++) {
            String nonStarP = patternP[i];
            int matchPos = findFirstMatch(s, nonStarP);
            if (matchPos < 0) {
                return false;
            } else {
                s = s.substring(matchPos + nonStarP.length());
            }
        }
        // if last have *,  or s is all matched
        return p.charAt(p.length() - 1) == '*' || s.length() == 0;
    }

    private int findFirstMatch(String s, String p) {
        // p does not contains *
        for (int i = 0; i <= s.length() - p.length(); i++) {
            // test substirng and p
            boolean isMatch = true;
            for (int j = 0; j < p.length(); j++) {
                char chS = s.charAt(i + j);
                char chP = p.charAt(j);
                if (chP != '?' && chS != chP) {
                    isMatch = false;
                    break;
                }
            }
            if (isMatch) { // if found match
                return i;
            }
        }
        return -1;
    }
}

Mistakes:
1: 当方法2的时候，没有考虑这种情况

Input：	"", ""
Output:	false
Expected:	true

2：方法2的时候， 由于没有考虑到 p = "*"的情况。
而我们初始条件的startIndex = 0 是第一个valid情况。 而每次startIndex跳到下一个情况（或者越出右边界一位）
这样，就产生了错误。

3： 在用s的startIndex ==0 的初始情况的时候，没有考虑，当s为空的情况。 导致error.

4: when the substring is "?", at first ,we simply skip to next, but it is WRONG. we need also check whether s has the character with it.

5: 当遇到?的时候，我们仅仅startIndex跳到下一个了， 可是，没有注意
s="aa"
p ="*?"的情况时，我们需要多跳几个。  因此，还是需要把*?的顺序，调整成？*

Learned:
1： 好像在leetcode里，不用考虑，输入是null  的情况。
2:
         s = "aa";
         System.out.println( s.lastIndexOf("a", 0));
这里，很诡异的，输出竟然是0  而不是1.  ----------------原因如下。

public int lastIndexOf(String str, int fromIndex)

Returns the index within this string of the last occurrence of the specified substring, searching backward starting at the specified index. 


 -----------------第二遍-----------
1： 用 * 来split ，  命令要写成：   str.split("\\*");    -------- 要用双反斜线
2： 注意， split函数，是可以得到数组的某个元素为 “”的。


  --------------------------------下面 是 别人的代码------------ C++------------

Analysis:

For each element in s
If *s==*p or *p == ? which means this is a match, then goes to next element s++ p++.
If p=='*', this is also a match, but one or many chars may be available, so let us save this *'s position and the matched s position.
If not match, then we check if there is a * previously showed up,
       if there is no *,  return false;
       if there is an *,  we set current p to the next element of *, and set current s to the next saved s position.

e.g.

abed
?b*d**

a=?, go on, b=b, go on,
e=*, save * position star=3, save s position ss = 3, p++
e!=d,  check if there was a *, yes, ss++, s=ss; p=star+1
d=d, go on, meet the end.
check the rest element in p, if all are *, true, else false;

Note that in char array, the last is NOT NULL, to check the end, use  "*p"  or "*p=='\0'".

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        const char* star=NULL;
        const char* ss=s;
        while (*s){
            if ((*p=='?')||(*p==*s)){s++;p++;continue;}
            if (*p=='*'){star=p++; ss=s;continue;}
            if (star){ p = star+1; s=++ss;continue;}
            return false;
        }
        while (*p=='*'){p++;}
        return !*p;
    }
};

-------------------------------------------------第三遍----------------想利用上面的想法， 也用递归来做的。结果还是超时。----------------------------然后就又是按照* 来split，然后线性查找即可--------  因此，这道题目，复杂度应该是在O(n)的--------------

对于前后的non- start string 的问题，我们事先匹配后，消去即可。

public class Solution { 
    public boolean isMatch(String s, String p) {
        if(p.length()==0)
            return s.length()==0;
        if(s.length()==0)
            return p.charAt(0)=='*' && isMatch(s,p.substring(1));
        if(p.charAt(0) !='*'){// delete all before first *
            return (p.charAt(0)=='?' || p.charAt(0)==s.charAt(0)) && isMatch(s.substring(1),p.substring(1));
        }
        if(p.charAt(p.length()-1) !='*'){ // delete all after last *
            char ch = p.charAt(p.length()-1);
            return (ch=='?' || ch ==s.charAt(s.length()-1)) && isMatch(s.substring(0,s.length()-1),p.substring(0,p.length()-1));
        }
        // now at the two end of p,  are *
        String[] P = p.split("\\*");
        int firstMatchPos = 0;
        for(int i =0;i< P.length; i++){
            if( P[i].length()==0)
                continue;
            firstMatchPos = findMatch(s, firstMatchPos,P[i]);
            if(firstMatchPos<0)
                return false;
            firstMatchPos += P[i].length();
        }
        return true;
    }
    private int findMatch(String s, int start, String p){// this p does not contain *
        for(int i =start;i <= s.length()-p.length();i++){
            //check the whole p
            boolean found = true;
            for(int j=0;j<p.length();j++){
                if( p.charAt(j) !='?' && p.charAt(j) != s.charAt(j+i)){
                    found = false;
                }
            }
            if(found)
                return i;
        }
        return -1;
    }
}

-------------------------------又一种思路---------------------
贪心的策略，能匹配就一直往后遍历，匹配不上了就看看前面有没有'*'来救救场，再从'*'后面接着试。
这个解法，其实就是我们最上面的哪种，但是，用两个index而不用递归，大大节省了时间。

public class Solution {
    public boolean isMatch(String s, String p) {
        int i = 0, j = 0;
        int star = -1, mark = -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) == '*') {
                star = j++;
                mark = i;
            } else if (star != -1) {
                j = star + 1;
                i = ++mark;
            } else {
                return false;
            }
        }
        while (j < p.length() && p.charAt(j) == '*') {
            ++j;
        }
        return j == p.length();
    }
}