动态规划10：通配符匹配问题

前言

在动态规划系列的前九篇文章中，我们分别学习了爬楼梯问题、最长公共子序列、01背包问题、最长递增子序列、不同路径问题、股票买卖问题、编辑距离问题、回文子串问题和区间DP问题。

今天我们将探讨动态规划中另一个经典的字符串匹配问题——通配符匹配问题。这个问题在文件系统、正则表达式、数据库查询等领域都有广泛应用，是理解模式匹配算法的重要基础。

问题描述

通配符匹配问题的核心是判断一个字符串是否能匹配一个包含通配符的模式。

基本规则

'?' 匹配任何单个字符
'*' 匹配任意数量的字符（包括零个）
其他字符必须精确匹配

问题定义

给定一个字符串 s 和一个字符模式 p，实现一个支持 '?' 和 '*' 匹配的通配符匹配。

示例：

输入: s = "adceb", p = "*a*b*"
输出: true
解释: 第一个 '*' 匹配空字符串, 第二个 '*' 匹配 "dce".

输入: s = "acdcb", p = "a*c?b"
输出: false

解法分析

思路一：递归解法

最直观的思路是使用递归来处理每种情况：

function isMatch(s, p) {
    return match(s, 0, p, 0);
    
    function match(s, i, p, j) {
        // 递归终止条件
        if (j === p.length) {
            return i === s.length;
        }
        
        if (p[j] === '*') {
            // '*' 匹配0个、1个或多个字符
            return match(s, i, p, j + 1) || 
                   (i < s.length && match(s, i + 1, p, j));
        } else if (i < s.length && (p[j] === '?' || p[j] === s[i])) {
            // 字符匹配或'?'匹配
            return match(s, i + 1, p, j + 1);
        }
        
        return false;
    }
}

复杂度分析：

时间复杂度：O(2^(m+n))，其中 m、n 分别是字符串和模式的长度
空间复杂度：O(m+n)，递归栈的深度

思路二：记忆化递归

递归解法存在大量重复计算，我们可以使用记忆化来优化：

function isMatch(s, p) {
    const memo = new Map();
    
    return match(s, 0, p, 0);
    
    function match(s, i, p, j) {
        const key = `${i}-${j}`;
        if (memo.has(key)) {
            return memo.get(key);
        }
        
        let result;
        if (j === p.length) {
            result = i === s.length;
        } else if (p[j] === '*') {
            result = match(s, i, p, j + 1) || 
                    (i < s.length && match(s, i + 1, p, j));
        } else if (i < s.length && (p[j] === '?' || p[j] === s[i])) {
            result = match(s, i + 1, p, j + 1);
        } else {
            result = false;
        }
        
        memo.set(key, result);
        return result;
    }
}

复杂度分析：

时间复杂度：O(m×n)
空间复杂度：O(m×n)

动态规划解法

状态定义

定义 dp[i][j] 表示字符串 s 的前 i 个字符是否能匹配模式 p 的前 j 个字符。

状态转移

根据模式字符的不同情况进行状态转移：

当 p[j-1] === '*' 时：
- dp[i][j] = dp[i][j-1]（* 匹配0个字符）
- dp[i][j] = dp[i-1][j]（* 匹配多个字符）
当 p[j-1] === '?' 或 p[j-1] === s[i-1] 时：
- dp[i][j] = dp[i-1][j-1]
其他情况：
- dp[i][j] = false

代码实现

function isMatch(s, p) {
    const m = s.length;
    const n = p.length;
    
    // 创建DP数组
    const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(false));
    
    // 初始化
    dp[0][0] = true;  // 空字符串匹配空模式
    
    // 处理模式以'*'开头的情况
    for (let j = 1; j <= n; j++) {
        if (p[j - 1] === '*') {
            dp[0][j] = dp[0][j - 1];
        }
    }
    
    // 填充DP表
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (p[j - 1] === '*') {
                // '*' 可以匹配0个或多个字符
                dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
            } else if (p[j - 1] === '?' || p[j - 1] === s[i - 1]) {
                // 字符匹配或'?'匹配
                dp[i][j] = dp[i - 1][j - 1];
            }
            // 其他情况dp[i][j]保持false
        }
    }
    
    return dp[m][n];
}

执行过程示例

以 s = "adceb", p = "*a*b*" 为例：

    ""  *  a  *  b  *
""   T  T  F  F  F  F
a    F  T  T  T  F  F  
d    F  T  F  T  F  F
c    F  T  F  T  F  F
e    F  T  F  T  F  F
b    F  T  F  T  T  T

步骤解析：

dp[0][0] = true：空字符串匹配空模式
dp[0][1] = true：空字符串匹配 *（匹配0个字符）
dp[1][2] = true：字符 a 匹配模式 *a
最终 dp[5][5] = true

空间优化

由于每个状态只依赖于上一行的状态，我们可以使用滚动数组优化空间：

function isMatch(s, p) {
    const m = s.length;
    const n = p.length;
    
    // 只需要两行
    let prev = Array(n + 1).fill(false);
    let curr = Array(n + 1).fill(false);
    
    prev[0] = true;
    
    // 处理模式以'*'开头的情况
    for (let j = 1; j <= n; j++) {
        if (p[j - 1] === '*') {
            prev[j] = prev[j - 1];
        }
    }
    
    for (let i = 1; i <= m; i++) {
        curr[0] = false;  // 非空字符串不能匹配空模式
        
        for (let j = 1; j <= n; j++) {
            if (p[j - 1] === '*') {
                curr[j] = curr[j - 1] || prev[j];
            } else if (p[j - 1] === '?' || p[j - 1] === s[i - 1]) {
                curr[j] = prev[j - 1];
            } else {
                curr[j] = false;
            }
        }
        
        // 交换数组
        [prev, curr] = [curr, prev];
    }
    
    return prev[n];
}

优化后复杂度：

时间复杂度：O(m×n)
空间复杂度：O(n)

算法优化技巧

1. 模式预处理

function preprocessPattern(pattern) {
    // 去除连续的'*'
    let result = '';
    let prevStar = false;
    
    for (let char of pattern) {
        if (char === '*') {
            if (!prevStar) {
                result += char;
                prevStar = true;
            }
        } else {
            result += char;
            prevStar = false;
        }
    }
    
    return result;
}

2. 早期终止优化

function isMatchOptimized(s, p) {
    // 预处理模式
    p = preprocessPattern(p);
    
    // 如果模式不包含'*'，长度必须相等
    if (!p.includes('*') && s.length !== p.length) {
        return false;
    }
    
    return isMatch(s, p);
}

复杂度对比

方法	时间复杂度	空间复杂度	特点
递归	O(2^(m+n))	O(m+n)	简单但效率低
记忆化递归	O(m×n)	O(m×n)	自顶向下，易理解
动态规划	O(m×n)	O(m×n)	自底向上，系统性强
空间优化DP	O(m×n)	O(n)	最优空间效率

实际应用场景

1. 文件系统

# 查找所有.js文件
ls *.js

# 查找特定模式的文件
find . -name "test*.py"

2. 数据库查询

1
2
3

-- SQL中的LIKE操作符类似通配符匹配
SELECT * FROM users WHERE name LIKE 'John%';
SELECT * FROM files WHERE path LIKE '*/config/*';

3. 配置文件匹配

// 路由匹配
const routes = [
    { path: '/api/*', handler: apiHandler },
    { path: '/static/*.css', handler: cssHandler },
    { path: '/user/*/profile', handler: profileHandler }
];

function matchRoute(url) {
    return routes.find(route => isMatch(url, route.path));
}

总结

通配符匹配问题展现了动态规划在字符串处理中的强大能力：

问题特征：具有最优子结构和重叠子问题
状态设计：二维DP表示前缀匹配关系
转移方程：根据字符类型分情况讨论
优化空间：利用状态依赖关系压缩空间

这个问题不仅在算法面试中常见，在实际开发中也有广泛应用。掌握了通配符匹配，你就掌握了一类重要的字符串匹配算法。

在下一篇文章中，我们将继续探讨动态规划的其他经典问题，敬请期待！

练习建议

在LeetCode上练习相关的字符串匹配题目
尝试实现文件名匹配功能
探索正则表达式的实现原理
思考如何优化大规模数据的模式匹配