44. 通配符匹配

二哥曾说，心胸开阔一点，别斤斤计较，以前很喜欢的一个博主，书的写不错，

但心胸是真的狭隘，还是二哥老乡，以前拿他做偶像，现在看来，有些人真的是

徒有其名。不然好好刷 LeetCode 吧，这里没有烦恼。

题意

给你一个输入字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 匹配规则的通配符

匹配：

'?' 可以匹配任何单个字符。

'*' 可以匹配任意字符串（包括空字符序列）。

判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹

配）。

难度

困难

示例

示例 1:

输入: s = "aa" p = "a"

输出: false

解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入: s = "aa" p = "*"

输出: true

解释: '*' 可以匹配任意字符串。

示例 3：

输入: 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 个字符全是 * 时才能匹配。

来看代码：

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 是否匹配。

来看一下题解效率：

044.通配符匹配-20240904154848.png

总结

本次我们再次利用了 动态规划 的方法来解决字符串问题，实际上这个问题被我们剖析为

三种情况，一种是普通的字符串完全匹配，一种是带有问号的，最后一种则是带有*的，

前面两个问题都解决了之后，我们再来面对*这个大 Boss，这样就比直接硬抗整个大问题

变得更加容易去解决。

力扣链接：https://leetcode.cn/problems/wildcard-matching/