［抄题］：
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:
-
scould be empty and contains only lowercase lettersa-z. -
pcould be empty and contains only lowercase lettersa-z, and characters like?or*.
Example 1:
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
Input:
s = "aa"
p = "*"
Output: true
Explanation: '*' matches any sequence.
Example 3:
Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
Example 4:
Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
Example 5:
Input:
s = "acdcb"
p = "a*c?b"
Output: false
[暴力解法]：
时间分析：
空间分析：
[优化后]：
时间分析：
空间分析：
［奇葩输出条件］：
［奇葩corner case］：
初始化dp[0][j]的时候，除开一直是*的情况，都不能随意匹配
［思维问题］：
搞不清楚和第十题的区别：就是能不能遗传 dp[i][j] = dp[i][j - 2]就行了
［英文数据结构或算法，为什么不用别的数据结构或算法］：
［一句话思路］：
［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：
［画图］：
［一刷］：
- dp[i][j - 1] 是重复一个字符的情况（其中包括了空字符），所以空字符不需要单独列出来
［二刷］：
［三刷］：
［四刷］：
［五刷］：
[五分钟肉眼debug的结果]：
［总结］：
- dp[i][j - 1] 是重复一个字符的情况（其中包括了空字符），所以空字符不需要单独列出来
［复杂度］：Time complexity: O(mn) Space complexity: O(mn)
［算法思想：递归/分治/贪心］：贪心
［关键模板化代码］：
for (int i = 1; i <= m; i++) {
dp[i][0] = false;
}
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) == '*') dp[0][j] = true;
else break;
}
［其他解法］：
［Follow Up］：
［LC给出的题目变变变］：
10有前序的
[代码风格] ：
[是否头一次写此类driver funcion的代码] ：
class Solution {
public boolean isMatch(String s, String p) {
//ini: dp[][]
int m = s.length();
int n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
//cc: dp[0][0], dp[0][], dp[][0]
dp[0][0] = true;
for (int i = 1; i <= m; i++) {
dp[i][0] = false;
}
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) == '*') dp[0][j] = true;
else break;
}
//for loop: not * must equal or ., * 0 or more
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++)
if (p.charAt(j - 1) != '*') {
//1s
dp[i][j] = dp[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?');
}else {
//multiple s, 0 s
dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
}
}
//return m n
return dp[m][n];
}
}