Given an input string (s) and a pattern (p), 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).

Note:

• s could be empty and contains only lowercase lettersa-z.
• pcould be empty and contains only lowercase lettersa-z, and characters like? or *.

递归，但是会超时

class Solution {
    public boolean isMatch(String s, String p) {
        if(p.length() == 0)
            return s.length() == 0;

        if(p.charAt(0) != '*') {
            if(s.length() == 0)
                return false;

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

            return false;
        } else {
            if(isMatch(s, p.substring(1)))
                return true;

            for(int i = 1; i <= s.length(); i++) {
                if(isMatch(s.substring(i), p.substring(1)))
                    return true;
            }

            return false;
        }
    }
}

DP

class Solution {
    public boolean isMatch(String s, String p) {
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        dp[s.length()][p.length()] = true;

        for(int i = s.length(); i >= 0; i--) {
            for(int j = p.length() - 1; j >= 0; j--) {
                if(p.charAt(j) != '*') {
                    if(i < s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?'))
                        dp[i][j] = dp[i + 1][j + 1];
                    else
                        dp[i][j] = false;
                } else {
                    if(dp[i][j + 1]) {
                        dp[i][j] = true;
                    } else {
                        for(int k = 0; i + k <= s.length(); k++) {
                            if(dp[i + k][j]) {
                                dp[i][j] = true;
                                break;
                            }
                        }
                    }

                }
            }
        }

        return dp[0][0];
    }
}