通配符 DP 匹配原理

通配符动态规划（DP）匹配的核心在于处理带有通配符（如*和?）的模式串与目标串的匹配问题。?匹配任意单个字符，*匹配任意长度字符（包括空串）。动态规划表dp[i][j]表示模式串前i个字符与目标串前j个字符是否匹配。

状态转移方程：

• 若pattern[i-1] == '?'或pattern[i-1] == text[j-1]：dp[i][j] = dp[i-1][j-1]
• 若pattern[i-1] == '*'：dp[i][j] = dp[i][j-1] || dp[i-1][j]

Java 工具类实现

以下是一个集成了通配符匹配功能的工具类，支持高效开发场景：

public class WildcardMatcher {
    public static boolean isMatch(String text, String pattern) {
        int m = text.length(), n = pattern.length();
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;
        
        for (int i = 1; i <= n; i++) {
            if (pattern.charAt(i - 1) == '*') {
                dp[i][0] = dp[i - 1][0];
            }
        }
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (pattern.charAt(i - 1) == '?' || 
                    pattern.charAt(i - 1) == text.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (pattern.charAt(i - 1) == '*') {
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                }
            }
        }
        return dp[n][m];
    }
}

性能优化技巧

预处理模式串：合并连续的*为单个*以减少无效计算。例如将a***b?c优化为a*b?c。

记忆化搜索：对于递归实现的场景，使用备忘录避免重复计算。

public static boolean isMatchOptimized(String s, String p) {
    p = p.replaceAll("\\*+", "*"); // 合并连续*
    return isMatch(s, p);
}

实际应用场景

文件系统匹配：实现类似Unix的ls *.txt功能：

List<String> filteredFiles = files.stream()
    .filter(f -> WildcardMatcher.isMatch(f, "*.txt"))
    .collect(Collectors.toList());

API路由匹配：支持通配符路径匹配：

boolean isMatch = WildcardMatcher.isMatch("/api/v1/users/123", "/api/v1/users/*");

边界条件处理

空字符串处理：模式串*可匹配空字符串，但?不能。

大小写敏感：根据需求添加toLowerCase()统一大小写：

isMatch(text.toLowerCase(), pattern.toLowerCase());

测试用例设计

基本功能测试：

assertTrue(WildcardMatcher.isMatch("abc", "a?c"));
assertFalse(WildcardMatcher.isMatch("abc", "a*d"));

极端情况测试：

assertTrue(WildcardMatcher.isMatch("", "*"));
assertFalse(WildcardMatcher.isMatch("", "?"));