Problem

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).

Example

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

Note

递归和动规的方法没有研究，说一下较为直观的贪心算法。

用cs和cp两个指针分别标记s和p进行比较的位置，当cs遍历完s后，若cp也遍历完p，说明完全配对。

我们看一下while循环里的几个分支：

第一个if语句，若cp和cs指向的字符相等，或cp指向的字符为'?'，则说明这一位配对成功，两个指针继续前移；

第二个else if语句，当cp指向的字符为'*'，则后面字符的配对结果要受到影响，必须用star和match分别在p和s的当前位置，也就是cp和cs，进行标记。然后，cp前移，cs不动，为什么呢？因为，如果此时cp == p.length()，就已经可以结束while循环了；但若cp不是末位，那么p剩下的字符还要继续判断，至于cs，完全可以等到下一次成功配对字符后再移动；

第三个else if语句，这里最为费解。当p之前出现过star，且此时cp和cs完全无法配对的时候，就一起退回在star和match配对过的位置。再将cp和cs逐个加1继续比较，并将match后移。为什么star不用后移呢？因为star是大BOSS，可以任意和后面match走过的很多位配对下去呀；

最后一个else语句，返回false。但是这个false包含了哪些情况呢？其实，就是p中没有star且无法配对的情况。

再用一个while循环跳过p尾部的所有'*'，如果有的话。
最后，若cp走完p，说明完全配对。

Solution

Greedy

public class Solution {
    public boolean isMatch(String s, String p) {
        int cs = 0, cp = 0, star = -1, match = 0;
        while (cs < s.length()) {
            if (cp < p.length() && (p.charAt(cp) == s.charAt(cs) || p.charAt(cp) == '?')) {
                cs++;
                cp++;
            }
            else if (cp < p.length() && p.charAt(cp) == '*') {
                star = cp;
                match = cs;
                cp++;
            }
            else if (star != -1) {
                cp = star + 1;
                cs = match + 1;
                match++;
            }
            else return false;
        }
        while (cp < p.length() && p.charAt(cp) == '*') cp++;
        return cp == p.length();
    }
}

DP

public class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null || p == null) return false;
        int lens = s.length();
        int lenp = p.length();
        boolean[][] dp = new boolean[lens + 1][lenp + 1];
        boolean flag = false;
        for (int i = 0; i <= lens; i++) {
            flag = false;
            for (int j = 0; j <= lenp; j++) {
                if (i == 0 && j == 0) {
                    dp[i][j] = true;
                    flag = true;
                    continue;
                }
                if (j == 0) {
                    dp[i][j] = false;
                    continue;
                }
                if (i == 0) dp[i][j] = dp[i][j - 1] && p.charAt(j - 1) == '*';
                else dp[i][j] = (matchChar(s.charAt(i - 1), p.charAt(j - 1)) && dp[i - 1][j - 1]) 
                                || (p.charAt(j - 1) == '*' && (dp[i][j - 1] || dp[i - 1][j]));    
                if (dp[i][j]) flag = true;
                if (dp[i][j] && p.charAt(j - 1) == '*' && j == lenp) return true;
            }
            if (!flag) return false;
        }
        return dp[lens][lenp];
    }
    public static boolean matchChar(char c, char p) {
        return (p == '?' || p == c);
    }
}