题目
给定一个字符串?(s)?和一个字符模式?(p)?，实现一个支持?'?'?和?'*'?的通配符匹配。'?'?可以匹配任何单个字符。
'*'?可以匹配任意字符串（包括空字符串）。两个字符串完全匹配才算匹配成功。?
说明: s 可能为空，且只包含从 a-z 的小写字母。p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和?*。
示例?1:
输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
https://leetcode-cn.com/problems/wildcard-matching/
分析
典型的动态规划题，做这道题费劲的不是找出规律写出动态方程，而是填充边界值。
先看怎么定义状态数组，示例1中?s = "adceb"? p = "*a*b"，那它们对应关系如下图：
因为题目说明s,p都可能为空，所以状态数组大小需要加1：
boolean[][] dp = new boolean[p.length()+1][s.length()+1];当s,p都为空时：
dp[0][0] = true;接下来是填充边界值，主要是为了处理前缀为*的情况，这种情况分两一个*或者多个连续的*：
for(int i=1;i<p.length();i++) {??if(p.charAt(i-1)?==?'*') {??//一个或者多个*都可以与空匹配?? dp[i][0] = true;??}else {?? break;??}}
填充完后，上图的状态图则变成如下：
状态方程
先分析最简单的情况，都为字母时：
//两字母相同if(p.charAt(i-1) == s.charAt(j-1)){????dp[i][j]?=?dp[i-1][j-1];?//只需要判断上一组是否匹配}else { //两字母不相同dp[i][j] = false;}
p为?时：
dp[i][j] = dp[i-1][j-1]; //只需要判断上一组是否匹配p为*时,它的作用可能会有两种，一种是表示为空，另外一种是一个或者多个字母：
//dp[i-1][j]?表示*为空//dp[i][j-1]??表示*是多个字母dp[i][j]?=?dp[i-1][j]?|| dp[i][j-1]
演示：
p = "*a*b"，p的长度为4，需要进行四层遍历
第一层遍历：i=1, p.charAt(i-1) = '*', 此时*表示一个或者多个字母，所以所有字母都可以跟它匹配得上，对s完成遍历后效果如下：（红色true）
第二层遍历：i=2, p.charAt(2-1) = 'a', 对s完成遍历后效果如下：（黄色true）
第三层遍历：i=3, p.charAt(3-1) = '*', 对s完成遍历后效果如下：（绿色true）
第四层遍历：i=4, p.charAt(4-1) = 'b', 对s完成遍历后效果如下：（蓝色true）
代码
class Solution {public boolean isMatch(String s, String p) {???? //因为题目说明s,p都可能为空，所以状态数组大小需要加1boolean[][] dp = new boolean[p.length()+1][s.length()+1];//s,p都为空时dp[0][0] = true;//处理前缀为*的情况，这种情况分两一个*或者多个连续的*for(int i=1;i<=p.length();i++){if(p.charAt(i-1) == '*'){//一个或者多个*都可以与空匹配dp[i][0] = true;}else {break;}}for(int i=1;i<=p.length();i++){for(int j=1;j<=s.length();j++) {if(p.charAt(i-1) == '?'){//只需要判断上一组是否匹配dp[i][j] = dp[i-1][j-1];}else if(p.charAt(i-1) == '*'){//dp[i-1][j] 表示*为空//dp[i][j-1] 表示*是多个字母dp[i][j] = dp[i-1][j] || dp[i][j-1];}else {//两字母相同if(p.charAt(i-1) == s.charAt(j-1)){dp[i][j] = dp[i-1][j-1]; //只需要判断上一组是否匹配}else { //两字母不相同dp[i][j] = false;}}}}return dp[p.length()][s.length()];}}
结果
