# 44 - Wildcard Matching

解法一 - Two pointer

這題直觀的做法是用兩個 pointer，一個指向 p，一個指向 s，就像我們用兩根手指頭指向兩個 string 去比對。

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length(), n = p.length();
        int i=0, j=0, star=-1, match;

        while(i < m) {
            // one-to-one match, keep going
            if(j<n && (s[i] == p[j] || p[j] == '?')) {
                i++;
                j++;
            }
            // 碰到 *，假設它 match 空字串 ""，用 star 記錄 * 位置，j 後移
            // 雖然 match = i，但意義上是假設 * match 到 ""，而非 s[i]
            // 若要理解，可以跟下一個 else if 部分中的 i = match 一起看
            else if(j<n && p[j] == '*') {
                match = i;
                star = j;
                j++;
            } 
            // 會進到這個條件，表示當前的 s[i] 跟 p[j] 無法 match
            // 而且也没有 *，所以 
            // s[i] 有可能是 match 到上一個 *(或 s[i] 前的某些 letter 要 match 到 *，s[i] 才能正確 match)
            // 做法是，首先將 j 回退到 * 的下一個位置
            // match 不能只是 match 剛遇到 * 的地方了，要多 match 一個 letter
            // i 回到 match，這步代表我們用 * match 了一個 letter
            else if(star >= 0) {
                j = star+1;  
                match++;
                i = match; 
            }
            else return false;
        }

        // If there are remaining *, we treat them as matches to ""
        while(j<n && p[j] == '*') j++;

        return j == n;
    }
};