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];
}
}
