友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
44. 通配符匹配
给你一个输入字符串 (s) 和一个字符模式 (p) ，请你实现一个支持 ? 和 * 匹配规则的通配符匹配：
-
?可以匹配任何单个字符。 -
*可以匹配任意字符序列（包括空字符序列）。
判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。
示例 1：
输入：s = "aa", p = "a" 输出：false 解释："a" 无法匹配 "aa" 整个字符串。
示例 2：
输入：s = "aa", p = "*" 输出：true 解释：'*' 可以匹配任意字符串。
示例 3：
输入：s = "cb", p = "?a" 输出：false 解释：'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
提示：
-
0 <= s.length, p.length <= 2000 -
s仅由小写英文字母组成 -
p仅由小写英文字母、?或*组成
思路分析
想使用双指针，发现行不通！
完全没有想到是动态规划！
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-06-24 19:57:05
*/
public boolean isMatch(String s, String p) {
int sl = s.length(), pl = p.length();
boolean[][] dp = new boolean[pl + 1][sl + 1];
dp[0][0] = true;
if (pl > 0 && p.charAt(0) == '*') {
Arrays.fill(dp[1], true);
}
for (int pi = 1; pi <= pl; pi++) {
if (p.charAt(pi - 1) == '*') {
dp[pi][0] = true;
} else {
break;
}
}
for (int pi = 1; pi <= pl; pi++) {
boolean patch = false;
for (int si = 1; si <= sl; si++) {
if (p.charAt(pi - 1) == '*') {
if (dp[pi - 1][0]) {
dp[pi][0] = true;
}
if (dp[pi - 1][si]) {
patch = true;
}
if (patch) {
dp[pi][si] = true;
}
}
if (p.charAt(pi - 1) == '?' || p.charAt(pi - 1) == s.charAt(si - 1)) {
dp[pi][si] = dp[pi - 1][si - 1];
}
}
}
return dp[pl][sl];
}
参考资料
-
44. 通配符匹配 - 官方题解 — 动态规划的思路与上一个题解一样，代码更简洁！
-
44. 通配符匹配 - 双指针贪心 — 这个贪心解法很简洁！