题目
给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
示例 1:输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。
示例 3:输入:
s = "cb"
p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
示例 4:输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
示例 5:输入:
s = "acdcb"
p = "a*c?b"
输出: false来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/wildcard-matching
思路
首先，题目里的复杂点有两个：问号和星号。但是问号其实是模糊匹配确定的一个字符，这个反而是一个非常简单的元素，所以星号才是真正使这个题变复杂的点。
这个问题一看就知道是可以进行分解成子问题的。我们按照逻辑上的自然顺序对s和p进行匹配，都是先从第一个字符开始匹配，考虑各种情况之后往后进行匹配，直到s和p都遍历完，确定可以匹配成功或者不成功为止。对于普通的a-z字符，直接对比即可；对于问号，直接当做匹配即可；对于星号，有三种情况，我们另indexS为s的遍历指针，indexP为p的遍历指针：（1）星号包含s的当前字符且包含之后的字符，则indexS+1， indexP不变（2）星号不包含s的当前字符，则indexS不变，indexP+1（3）星号正好与s的当前字符匹配，则indexS+1，indexP+1。其实第三种情况可以被钱两种情况的组合覆盖到，所以只需要保留前两种情况即可。
这时候我们就可以开始写代码实现了。但是上面的流程中很显然有很多重复的计算，所以我们需要做一下剪枝。比如已经判断过indexS到s.length的字符串与indexP到p.length的pattern是匹配的，就可以记录下来，下次不需要重新计算。
上面的代码实现显然是用递归实现，那么就需要考虑递归的结束条件：（1）如果s和p都已经遍历完成，那么就说明已经匹配成功（2）如果p遍历完成，s没有遍历完成，那么说明匹配失败（3）如果s遍历完成，p的剩余字符都是星号，那么匹配也是成功，否则匹配失败
到此，整个代码的流程就已经确定了。
额外的，我们可以写一下状态转移方程。上面过程中我们提到动态规划，但是最终使用了剪枝方法，是用到了动态规划的思想的。那么总结成动态规划的状态转移方程是完全有必要的。其实我认为动态规划的问题最难就在于把问题归纳为一个数学题，比如我们上面的思路其实是在求解这样一个问题：对于s和p，求解s[0,end]和p[0,end]的匹配情况，因为end是确定的，所以可以忽略，也就是求解f(s0,p0)。我们泛化为求解f(si, pj)。在s[i]=p[j]或者p[j]=='?'的情况下，f(si,pj)=f(si+1,pj+1)；在p[j]='*'的情况下，f(si,pj)=f(si+1,pj) or f(si,pj+1)；其他情况下f(si,pj)=false。
我们看官方的解法，其实正好相反，我把end当作是确定的，他把0当作是确认的，所以题目被归纳为求解f(sn,pm)。然后泛化为求解f(si,pj)。在s[i]=p[j]或者p[j]=='?'的情况下，f(si,pj)=f(si-1,pj-1)；在p[j]='*'的情况下，f(si,pj)=f(si-1,pj) or f(si,pj-1)；其他情况下f(si,pj)=false。
这两个思路看起来一样，但我觉得官方的思路更好一些，因为这个思路是一个显式地逐步增加信息的过程，用f(si,pj)去往前推进。总结当前信息，然后向下推进，这种可以用迭代的方式实现，而不必是递归。
个人代码如下：
class Solution {
public boolean isMatch(String s, String p) {
// 用于记录s[i,end]和p[j,end]的匹配情况；0代表未知，1代表匹配，-1代表不匹配
int[][] matchCase = new int[s.length()][p.length()];
return isMatch(s, 0, p, 0, matchCase);
}
public boolean isMatch(String s, int indexS, String p, int indexP, int [][]matchCase) {
// s已遍历完，p也遍历完则match；p剩余全是星号则匹配，否则不匹配
if (indexS == s.length()) {
if (indexP == p.length()) {
return true;
} else {
while (indexP < p.length()) {
if (p.charAt(indexP) != '*') {
return false;
}
indexP++;
}
return true;
}
}
// p遍历完，s没遍历完，则不匹配
if (indexP == p.length()) {
return false;
}
// 剪枝，使用已经计算过的结果
if (matchCase[indexS][indexP] != 0) {
return matchCase[indexS][indexP] == 1;
}
char charS = s.charAt(indexS);
char charP = p.charAt(indexP);
boolean match = false;
if (charP == charS || charP == '?') {
match = isMatch(s, indexS + 1, p, indexP + 1,matchCase);
} else if (charP == '*') {
match = isMatch(s, indexS + 1, p, indexP + 1,matchCase) || isMatch(s, indexS, p, indexP + 1,matchCase) || isMatch(s, indexS + 1, p, indexP,matchCase);
}
matchCase[indexS][indexP] = match ? 1 : -1;
return match;
}
public static void main(String[] args) {
String s = "adceb";
String p = "*a*b";
System.out.println(new Solution().isMatch(s,p));
}
}复杂度
时间复杂度：O(mn)
空间复杂度：O(mn)
耗时：78分钟