字符串匹配 DP：通配符与正则

正则表达式匹配（LeetCode 10）

支持 .（匹配任意单字符）和 *（匹配前一个字符出现0次或多次）：

public boolean isMatch(String s, String p) {
    int m = s.length(), n = p.length();
    // dp[i][j]: s[0..i-1] 与 p[0..j-1] 是否匹配
    boolean[][] dp = new boolean[m+1][n+1];
    dp[0][0] = true;
    // 处理 p 中 x* 可以匹配空字符串的情况
    for (int j = 2; j <= n; j += 2)
        if (p.charAt(j-1) == '*') dp[0][j] = dp[0][j-2];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            char sc = s.charAt(i-1), pc = p.charAt(j-1);
            if (pc == '*') {
                // '*' 配 0 个：dp[i][j-2]
                // '*' 配 1+个：需要 p[j-2] 匹配当前 s[i-1]
                dp[i][j] = dp[i][j-2]
                        || ((pc == '.' || sc == p.charAt(j-2)) && dp[i-1][j]);
                // 注意：此处 pc 是 '*'，前字符是 p.charAt(j-2)
                dp[i][j] = dp[i][j-2]
                        || ((p.charAt(j-2) == '.' || p.charAt(j-2) == sc) && dp[i-1][j]);
            } else {
                // 直接匹配
                dp[i][j] = dp[i-1][j-1] && (pc == '.' || pc == sc);
            }
        }
    }
    return dp[m][n];
}

通配符匹配（LeetCode 44）

? 匹配任意单字符，* 匹配任意字符串（含空）：

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] = true;
    // p 中连续的 '*' 可以匹配空字符串
    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 sc = s.charAt(i-1), pc = p.charAt(j-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 {
                dp[i][j] = dp[i-1][j-1] && (pc == '?' || pc == sc);
            }
        }
    }
    return dp[m][n];
}

两题对比

解题技巧

• 两题均用二维 DP，dp[i][j] 表示从字符串首部子串的匹配结果
• 初始化时注意 dp[0][j] 的含义：空字符串 s 与 p 的前 j 个字符是否匹配
• * 的两种情况：匹配 0 次（看 dp[i][j-1] 或 dp[i][j-2]）、匹配多次（看 dp[i-1][j]）