动态规划：外卡匹配

https://leetcode.com/problems/wildcard-matching/
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).

class Solution {
    public boolean isMatch(String s, String p) {
        //使用动态规划来解题。dp[m][n]表示s.subString(0,len-m)和p.subString(0,len-n)匹配
        boolean[][] dp = new boolean[s.length()+1][p.length()+1];
        dp[s.length()][p.length()] = true;
        for(int i =  p.length()-1;i>=0;i--){
            if(p.charAt(i) != '*'){
                break;
            }else{
                dp[s.length()][i] = true;
            }
        }
        for(int i = s.length()-1;i>=0;i--){
            for(int j = p.length()-1;j>=0;j--){
                if(s.charAt(i) == p.charAt(j) || p.charAt(j) == '?'){
                    dp[i][j] = dp[i+1][j+1];
                }else if(p.charAt(j) == '*'){
                    dp[i][j] = dp[i+1][j] || dp[i][j+1];
                }
            }
        }
        return dp[0][0];
    }
}