044.通配符匹配
作者：沉默王二
发布时间：2024-09-04T16:08:24.330+0800
二哥曾说，心胸开阔一点，别斤斤计较，以前很喜欢的一个博主，书的写不错，但心胸是真的狭隘，还是二哥老乡，以前拿他做偶像，现在看来，有些人真的是徒有其名。不然好好刷 LeetCode 吧，这里没有烦恼。
题意
给你一个输入字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符序列）。
判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。
难度
困难
示例
示例 1:
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
输入: s = "aa" p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
输入: s = "aa" p = ""
输出: true
解释: '' 可以匹配任意字符串。
示例 3：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
输入: s = "cb" p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
### 分析
其实我们很早就做过一到正则表达式的题：010.正则式匹配 ，大家还有印象吗？
当时是 . 和 *，现在是 ? 和 *。
10 中的 * 用来匹配零个或多个前面的那一个字符。
44 中的 * 用来匹配任意字符串，包括空字符串。
符号相同，但寓意上有所不同。
10 中的 . 可以匹配任意单个字符，而 44 中的 ? 也可以匹配任意单个字符。
符号不同，但寓意上完全相同。
10 题我们用了动态规划，这道题仍然可以用动态规划来解。
普通字符：需要和 s 中同一位置的字符完全匹配
'?'：能够匹配 s 中同一位置的任意字符
'*'：能够匹配任意字符串
前面两种情况都比较简单，因为只需要拿 p 中的同位置字符和 s 中的同位置字符进行比较即可。只要 p[i] == s[i] 或者 p[i] == '?'，那么就是匹配的。
但是 * 就比较复杂了，因为 * 可以匹配任意字符串，包括空字符串。所以我们需要考虑 * 匹配 0 个字符、1 个字符、2 个字符、...、n 个字符的情况。
假设在模式 p 中某个位置 p[j] 是 *，此时我们需要考虑多种匹配可能性：
- 匹配 0 个字符：即 p[j] 和 s[i] 的当前字符没有匹配上，* 作为空字符被忽略，匹配下一个模式字符。这个可以通过 dp[i][j] = dp[i][j-1] 实现，即认为 * 匹配了空字符。
- 匹配 1 个或多个字符：p[j] 匹配了 s[i] 中的一个字符，然后继续考虑 * 是否可以继续匹配更多字符。这可以通过 dp[i][j] = dp[i-1][j] 实现，即 * 匹配了当前的字符，还可以继续匹配后面的字符。
我们定义一个二维布尔数组 dp，其中 dp[i][j] 表示字符串 s 的前 i 个字符与模式 p 的前 j 个字符是否匹配。
然后来定义转移方程：
如果 p[j - 1] == s[i - 1] 或者 p[j - 1] == '?'，则 dp[i][j] = dp[i - 1][j - 1]。
如果 p[j - 1] == ''，则 dp[i][j] = dp[i - 1][j]（ 匹配一个字符）或 dp[i][j - 1]（* 匹配空字符）。
否则，dp[i][j] = false。
初始化状态：
dp[0][0] = true，因为空字符串和空模式是匹配的。
dp[0][j]：对于空字符串，只有当模式 p 的前 j 个字符全是 * 时才能匹配。
来看代码：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length(), n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
// 初始化 dp[0][0]，表示空字符串和空模式匹配
dp[0][0] = true;
// 初始化第一行：只有当 p 的前 j 个字符全为 '*' 时，dp[0][j] 为 true
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) == '*') {
dp[0][j] = dp[0][j - 1];
}
}
// 填充 dp 表
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '?') {
dp[i][j] = dp[i - 1][j - 1]; // 匹配当前字符
} else if (p.charAt(j - 1) == '*') {
dp[i][j] = dp[i - 1][j] || dp[i][j - 1]; // * 匹配一个或多个字符
}
}
}
// 最终结果
return dp[m][n];
}
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.isMatch("aa", "a")); // 输出 false
System.out.println(solution.isMatch("aa", "*")); // 输出 true
System.out.println(solution.isMatch("cb", "?a")); // 输出 false
System.out.println(solution.isMatch("adceb", "*a*b")); // 输出 true
System.out.println(solution.isMatch("acdcb", "a*c?b")); // 输出 false
}
}
来解释一下：
①、初始化 dp 数组：
dp[0][0] = true：表示空字符串和空模式匹配。
初始化 dp[0][j]，当模式 p 的前 j 个字符全是 * 时，dp[0][j] = true，因为 * 可以匹配空字符串。
②、状态转移方程：
如果 p[j - 1] == s[i - 1] 或 p[j - 1] == '?'，当前字符匹配，则 dp[i][j] = dp[i - 1][j - 1]。
如果 p[j - 1] == '*'，则 dp[i][j] = dp[i - 1][j] || dp[i][j - 1]，即 * 匹配一个或多个字符，或 * 匹配空字符。
③、最终结果：
返回 dp[m][n]，表示整个字符串 s 和模式 p 是否匹配。
来看一下题解效率：
总结
本次我们再次利用了 动态规划 的方法来解决字符串问题，实际上这个问题被我们剖析为三种情况，一种是普通的字符串完全匹配，一种是带有问号的，最后一种则是带有的，前面两个问题都解决了之后，我们再来面对这个大Boss，这样就比直接硬抗整个大问题变得更加容易去解决。
力扣链接：https://leetcode.cn/problems/wildcard-matching/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
PDF 版本目前只针对二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 加入我们吧。
一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 6100 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！
语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
这道题可以说完全重写了，给出 1 道大家完全都能掌握的题解（ 主要是理解接数列乘法的底层逻辑）。
增加代码注释，这样大家更容易看懂并掌握题解；
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
增加手绘图，这样大家更容易理解解题思路；
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。