通配符匹配（Wildcard Matching） 题目描述 给定一个字符串 s 和一个模式串 p ，模式串中可能包含以下两种通配符： '?' 可以匹配任意单个字符。 '*' 可以匹配任意长度的字符序列（包括空序列）。 要求判断字符串 s 是否能够被模式串 p 完全匹配。 示例 输入：s = "adceb", p = " a b" 输出：true 解释：' ' 匹配空序列和 "dce"，'a' 匹配 'a'，' ' 匹配 "b"，所以整个字符串被匹配。 解题过程 1. 定义状态 我们使用动态规划表 dp[i][j] ，其中： dp[i][j] 表示字符串 s 的前 i 个字符（即 s[0..i-1] ）是否能够被模式串 p 的前 j 个字符（即 p[0..j-1] ）匹配。 最终目标是求 dp[m][n] ，其中 m 是 s 的长度， n 是 p 的长度。 2. 初始化边界条件 dp[0][0] = true ：空字符串匹配空模式。 对于第一行（ i = 0 ，即 s 为空字符串）： 如果 p[j-1] 是 '*' ，则 dp[0][j] = dp[0][j-1] （因为 '*' 可以匹配空序列）。 否则 dp[0][j] = false 。 对于第一列（ j = 0 ，即 p 为空模式）： dp[i][0] = false （因为非空字符串无法被空模式匹配，除非 i=0 ）。 3. 状态转移方程 我们根据当前字符和模式字符的关系分类讨论： 如果 p[j-1] 是普通字符： 只有当 s[i-1] == p[j-1] 且 dp[i-1][j-1] 为真时， dp[i][j] = true 。 如果 p[j-1] 是 '?' ： 它匹配任意单个字符，所以只要 dp[i-1][j-1] 为真， dp[i][j] = true 。 如果 p[j-1] 是 '*' ： '*' 可以匹配空序列（即不使用 '*' ），此时 dp[i][j] = dp[i][j-1] 。 或者匹配一个或多个字符（即使用 '*' 匹配 s[i-1] ），此时 dp[i][j] = dp[i-1][j] 。 综上： dp[i][j] = dp[i][j-1] || dp[i-1][j] 。 4. 填充DP表 我们按行或按列填充整个 (m+1) x (n+1) 的DP表。以下是对示例 s = "adceb" , p = "*a*b" 的填充过程（用 T 表示 true， F 表示 false）： | s\p | "" | * | a | * | b | |-----|----|----|----|----|----| | "" | T | T | F | F | F | | a | F | T | T | T | F | | d | F | T | F | T | F | | c | F | T | F | T | F | | e | F | T | F | T | F | | b | F | T | F | T | T | 最终 dp[5][4] = true ，所以匹配成功。 5. 复杂度分析 时间复杂度：O(m × n)，需要填充整个DP表。 空间复杂度：O(m × n)，可以优化到 O(n)（只保留上一行）。 关键点 注意 '*' 的两种匹配方式：匹配空序列或匹配当前字符并继续使用 '*' 。 初始化时，空字符串与连续 '*' 的匹配需要正确处理。