跳至主要內容

通配符匹配——贪心与DP的对比及空间优化

老张2026/4/30大约 7 分钟

通配符匹配——贪心与DP的对比及空间优化

适读人群：Java后端工程师、Hard题进阶学习者 | 阅读时长：约20分钟 | 难度：Hard

开篇故事

通配符匹配（LeetCode 44）和正则匹配（LeetCode 10）是一对兄弟题，放在一起做特别有收获。

表面上看，两道题都是字符串匹配，都有 . 和 *，代码结构也很相似。但 * 的语义完全不同：正则匹配的 * 是"前一个字符出现0次或多次"，而通配符匹配的 * 是"匹配任意序列（包括空序列）"。

这一个语义的差异，导致处理 * 的转移方程截然不同，也导致贪心解法只能用在通配符匹配，而不能用在正则匹配。

我在面试中被问到这道题的时候，当时很自然地想到了贪心：遇到 * 时，记住当前位置，先让 * 匹配0个字符继续；如果后续匹配失败，回退到 * 的位置，让 * 多匹配一个字符再试。这是典型的"贪心+回退"策略，时间复杂度虽然理论上最坏是 O(mn)，但实践中非常快，代码也比DP简洁很多。

今天我把两种解法都讲透，重点放在对比分析上。

一、题目解析

题号：LeetCode 44. Wildcard Matching

题目描述：给你一个输入字符串 s 和一个字符规律 p，请你实现一个支持 ? 和 * 的通配符匹配。

  • ? 匹配任何单个字符
  • * 匹配任意字符序列（包括空字符序列）

示例：

  • 输入：s = "aa"，p = ""，输出：true（ 匹配 "aa"）
  • 输入：s = "cb"，p = "?a"，输出：false
  • 输入：s = "adceb"，p = "ab"，输出：true

与10题的关键区别：

LeetCode 10（正则）LeetCode 44（通配符）
* 语义前一个字符出现0/多次匹配任意字符序列
* 处理与前一字符绑定，成对出现独立出现，直接匹配任意字符
贪心可行？不可行可行

二、DP思路推导

2.1 状态定义

定义 dp[i][j] = s 的前 i 个字符能否被 p 的前 j 个字符完全匹配

2.2 状态转移方程

情况一：p[j-1] 是普通字母

dp[i][j] = dp[i-1][j-1] && (s[i-1] == p[j-1])

情况二：p[j-1] 是 ?

? 匹配任意单个字符：

dp[i][j] = dp[i-1][j-1]  （i > 0时，因为?必须消耗一个字符）

情况三：p[j-1] 是 *

* 可以匹配空序列或任意序列：

  • * 匹配空序列（0个字符）：等价于忽略 *，dp[i][j] = dp[i][j-1]
  • * 匹配1个或多个字符（消耗 s 的一个字符）：dp[i][j] = dp[i-1][j]

注意：和正则匹配的 * 不同，这里的 * 是独立的，不需要与前一个字符绑定。

dp[i][j] = dp[i][j-1] || dp[i-1][j]

完整转移方程：

dp[i][j] = dp[i-1][j-1]             if p[j-1] is letter and s[i-1]==p[j-1]
dp[i][j] = dp[i-1][j-1]             if p[j-1] == '?'  (i>0)
dp[i][j] = dp[i][j-1] || dp[i-1][j] if p[j-1] == '*'

2.3 边界条件

  • dp[0][0] = true：空串和空模式匹配
  • dp[0][j]：空串与模式。只有当模式是连续的 * 时才为 true
    dp[0][j] = dp[0][j-1] && p[j-1] == '*'
  • dp[i][0] = false（i > 0）：非空串与空模式不匹配

2.4 状态转移示意

s = "adceb", p = "*a*b"

     ""  *  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 ✓

三、解法一：标准二维DP

public class WildcardMatching {
    
    /**
     * 44. 通配符匹配 - 二维DP
     * 时间复杂度：O(m * n)
     * 空间复杂度：O(m * n)
     */
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        
        // 空串与模式匹配：只有连续的*才能匹配空串
        for (int j = 1; j <= n; j++) {
            dp[0][j] = dp[0][j - 1] && p.charAt(j - 1) == '*';
        }
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                char pc = p.charAt(j - 1);
                char sc = s.charAt(i - 1);
                
                if (pc == '*') {
                    // * 匹配0个字符（dp[i][j-1]）或1+个字符（dp[i-1][j]）
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                } else if (pc == '?' || pc == sc) {
                    // ? 或字符直接匹配
                    dp[i][j] = dp[i - 1][j - 1];
                }
                // 否则 dp[i][j] 保持 false
            }
        }
        
        return dp[m][n];
    }
}

Mermaid转移图：

四、解法二：空间优化（一维滚动）

/**
 * 44. 通配符匹配 - 空间优化到 O(n)
 */
public boolean isMatchOptimized(String s, String p) {
    int m = s.length();
    int n = p.length();
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;
    
    // 初始化第0行（空串）
    for (int j = 1; j <= n; j++) {
        dp[j] = dp[j - 1] && p.charAt(j - 1) == '*';
    }
    
    for (int i = 1; i <= m; i++) {
        boolean prev = dp[0];  // 保存dp[i-1][j-1]
        dp[0] = false;         // dp[i][0] = false（i>0时）
        
        for (int j = 1; j <= n; j++) {
            boolean temp = dp[j];  // 保存旧的dp[i-1][j]
            char pc = p.charAt(j - 1);
            char sc = s.charAt(i - 1);
            
            if (pc == '*') {
                dp[j] = dp[j - 1] || dp[j];  // dp[i][j-1] || dp[i-1][j]（dp[j]此时还是dp[i-1][j]）
            } else if (pc == '?' || pc == sc) {
                dp[j] = prev;  // dp[i-1][j-1]
            } else {
                dp[j] = false;
            }
            
            prev = temp;  // 下一轮的dp[i-1][j-1]就是本轮的dp[i-1][j]
        }
    }
    
    return dp[n];
}

五、解法三：贪心回退（O(1)空间）

贪心策略：遇到 * 时，记录 * 的位置（starJ）和当前文本位置（matchI）。先让 * 匹配0个字符。如果后续匹配失败，回退到 *，让 * 多匹配一个字符（matchI++）。

/**
 * 44. 通配符匹配 - 贪心回退法
 * 时间复杂度：O(m * n)（最坏情况）
 * 空间复杂度：O(1)
 */
public boolean isMatchGreedy(String s, String p) {
    int m = s.length();
    int n = p.length();
    int i = 0, j = 0;         // 当前s和p的指针
    int starJ = -1;            // 最近一个*在p中的位置
    int matchI = 0;            // *匹配时，s的起始位置
    
    while (i < m) {
        if (j < n && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
            // 普通字符或?匹配：两个指针同时前进
            i++;
            j++;
        } else if (j < n && p.charAt(j) == '*') {
            // 遇到*：记录位置，先让*匹配0个字符
            starJ = j;
            matchI = i;  // 记录此时s的位置
            j++;         // p前进（先跳过*）
        } else if (starJ != -1) {
            // 匹配失败，但有之前的*可以回退
            // 让*多匹配一个字符：matchI++，然后重新从starJ+1开始匹配模式
            matchI++;
            i = matchI;
            j = starJ + 1;
        } else {
            // 无法匹配且没有*可以回退
            return false;
        }
    }
    
    // 检查p中剩余的字符是否都是*
    while (j < n && p.charAt(j) == '*') j++;
    
    return j == n;
}

贪心与DP的对比：

特性DP贪心回退
时间复杂度O(mn)O(mn)（最坏）
空间复杂度O(mn)或O(n)O(1)
代码直觉性中高
适用范围正则+通配符仅通配符

六、正则匹配 vs 通配符匹配：* 的语义对比

通配符 * 的转移更简单：无需检查字符是否匹配，直接取两个方向的或。

七、踩坑实录

坑一：dp[0][j]初始化只考虑了第一个*

dp[0][j] = dp[0][j-1] && p[j-1]=='*'，这要求前面连续都是 *。如果模式是 *a*，dp[0][1]=true，dp[0][2]=false，dp[0][3]=false（a不是，所以中断了）。不能写成只看当前字符是不是。

坑二：贪心回退时matchI的更新

matchI 是"上一次 * 开始匹配时 s 的位置"，每次回退时 matchI++，代表让 * 多匹配一个字符。很多人在回退时写成 i++（直接移动 i）而忘记更新 matchI，导致后续回退次数不对。

坑三：贪心的终止检查

贪心结束后，i 到达了 m，但 j 可能没到达 n。此时需要检查 p 剩余部分是否全是 *（全是*才能匹配空余的空序列），不能直接返回 j == n。

八、总结

通配符匹配和正则匹配的核心区别在 * 的语义上：

  • 正则 *：与前字符绑定，转移时需要检查字符是否匹配
  • 通配符 *：独立的"任意序列"，转移时无条件取两方向的或

贪心回退是通配符匹配特有的高效解法，空间O(1)，代码直觉性强。但注意它不能用在正则匹配上（因为正则的 * 语义更复杂）。

编辑此页
最近更新:
贡献者: xiaozhangge