字符串 DP 进阶：回文子串、正则与通配符匹配

摘要

字符串 DP 是动态规划中应用场景最广泛的分支之一，面试高频出现。本文聚焦三个独立的核心主题：回文子串（区间 DP / 中心扩展）、正则表达式匹配（状态机建模 + DP）、通配符匹配（* 的贪心与 DP 两种解法对比）。三个主题都有各自的建模难点，正则匹配中 a* 的语义（“匹配零个或多个 a”）尤其容易出错。掌握本文内容，可应对 LeetCode 5、10、44、647、516 等高频题。

第 1 章回文子串与最长回文子串

1.1 回文子串计数（LeetCode 647）

LeetCode 647 - Palindromic Substrings（中等）

给定字符串 s，统计其中有多少个回文子串（包括单字符）。

输入: s = "abc"
输出: 3（每个字符本身是回文串）

输入: s = "aaa"
输出: 6（"a", "a", "a", "aa", "aa", "aaa"）

1.2 中心扩展法： $O (n^{2})$ 时间 $O (1)$ 空间

每个回文串都有一个中心（单字符中心或两字符中心）。枚举所有可能的中心，向两侧扩展，统计回文串数量。

public int countSubstrings(String s) {
    int n = s.length(), count = 0;
    for (int center = 0; center < 2 * n - 1; center++) {
        // center 是虚拟中心：
        // 偶数 center 对应字符位置 center/2（奇数长度回文串）
        // 奇数 center 对应两字符间隙（偶数长度回文串）
        int left = center / 2;
        int right = left + center % 2;  // 奇长度: right = left; 偶长度: right = left+1
 
        while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
            count++;
            left--;
            right++;
        }
    }
    return count;
}

另一种等价写法（更直观）：

public int countSubstrings(String s) {
    int n = s.length(), count = 0;
    // 枚举奇数长度回文串（以每个字符为中心）
    for (int i = 0; i < n; i++) {
        count += expand(s, i, i);
    }
    // 枚举偶数长度回文串（以每对相邻字符为中心）
    for (int i = 0; i < n - 1; i++) {
        count += expand(s, i, i + 1);
    }
    return count;
}
 
private int expand(String s, int left, int right) {
    int count = 0;
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        count++;
        left--;
        right++;
    }
    return count;
}

1.3 区间 DP 法：适合需要复用回文信息的场景

isPalin[i][j] = s[i..j] 是否是回文串，同矩阵路径DP：网格出发的二维状态转移中 LeetCode 132 的预计算方式：

boolean[][] isPalin = new boolean[n][n];
int count = 0;
// 从右下角往左上角填（确保 isPalin[i+1][j-1] 先算）
for (int i = n - 1; i >= 0; i--) {
    for (int j = i; j < n; j++) {
        if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || isPalin[i + 1][j - 1])) {
            isPalin[i][j] = true;
            count++;
        }
    }
}

适用场景：当后续需要频繁查询 isPalin[i][j] 时（如分割回文串 II），提前 $O (n^{2})$ 预计算，后续查询 $O (1)$ ，比每次单独调用中心扩展更高效。

1.4 最长回文子串（LeetCode 5）

LeetCode 5 - Longest Palindromic Substring（中等）

在中心扩展基础上，记录最长回文串的起点和长度：

public String longestPalindrome(String s) {
    int n = s.length();
    int start = 0, maxLen = 1;
 
    for (int center = 0; center < 2 * n - 1; center++) {
        int left = center / 2;
        int right = left + center % 2;
 
        while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
            if (right - left + 1 > maxLen) {
                maxLen = right - left + 1;
                start = left;
            }
            left--;
            right++;
        }
    }
    return s.substring(start, start + maxLen);
}

1.5 最长回文子序列（LeetCode 516）

LeetCode 516 - Longest Palindromic Subsequence（中等）

子序列（可不连续）与子串（必须连续）的区别在于转移方程不同。

状态：dp[i][j] = 字符串 s[i..j] 中最长回文子序列的长度。

转移：

若 s[i] == s[j]：两端字符相同，可加入子序列：dp[i][j] = dp[i+1][j-1] + 2
若 s[i] != s[j]：舍弃一端：dp[i][j] = max(dp[i+1][j], dp[i][j-1])

public int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
 
    // Base case：单字符
    for (int i = 0; i < n; i++) dp[i][i] = 1;
 
    // 区间 DP：从短到长
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][n - 1];
}

回文子串 vs 回文子序列

连续子串：中心扩展法 $O (n^{2})$ 时间 $O (1)$ 空间，或区间 DP $O (n^{2})$ 时间 $O (n^{2})$ 空间

不连续子序列：只能用区间 DP（无法用中心扩展），转移方程考虑”两端是否相等”

口诀：子串用扩展，子序列用区间 DP

第 2 章正则表达式匹配（LeetCode 10）

2.1 题目

LeetCode 10 - Regular Expression Matching（困难）

给定字符串 s 和模式串 p，实现支持 . 和 * 的正则表达式匹配。

. 匹配任意单个字符
* 匹配零个或多个前驱字符

要求完全匹配（不是部分匹配）。

s = "aa", p = "a"    → false（p 不能匹配多个字符）
s = "aa", p = "a*"   → true（"a*" 可以匹配两个 "a"）
s = "ab", p = ".*"   → true（".*" 匹配任意字符串）
s = "aab", p = "c*a*b" → true（"c*" 匹配 0 个 c，"a*" 匹配 2 个 a）

2.2 `*` 的语义陷阱

* 在标准正则表达式中的语义：a* 整体匹配 0 个或多个 a（不是”任意字符”）。* 不能单独出现，必须跟在一个字符后面（如 a*、.*）。

容易出错的情况：

"aab" vs "c*a*b"：c* 匹配 0 个 c，a* 匹配 2 个 a，b 匹配 1 个 b → true
"a" vs "ab*"：b* 匹配 0 个 b → true

2.3 状态定义与转移

状态：dp[i][j] = s[0..i-1]（前 i 个字符）是否与 p[0..j-1]（前 j 个模式字符）完全匹配。

使用 1-indexed 的优点：dp[0][0] = true（空串匹配空模式），边界处理更简洁。

Base Case：

dp[0][0] = true（空串与空模式匹配）
dp[i][0] = false（非空串与空模式不匹配），i > 0
dp[0][j]：空串与模式 p[0..j-1] 匹配。只有当 p[j-1] == '*' 时，dp[0][j] = dp[0][j-2]（* 消除前驱字符，使模式缩短 2）

转移方程（核心逻辑）：

情况一：p[j-1] 是普通字符或 .

p[j-1] 是普通字符时，s[i-1] 与 p[j-1] 必须精确匹配；p[j-1] == '.' 时匹配任意字符：

$d p [i] [j] = match (s [i - 1], p [j - 1]) && d p [i - 1] [j - 1]$

其中 match(a, b) = (a == b || b == '.')。

情况二：p[j-1] == '*'（最复杂的情况）

* 有两种使用方式：

使用 0 次：a* 整体不匹配任何字符，相当于 p[j-2] 和 p[j-1] 都不存在，即： $d p [i] [j] = d p [i] [j - 2]$
使用 1 次或多次：a* 匹配了 s[i-1]（即 s[i-1] 与 p[j-2] 匹配），然后 a* 还可以继续匹配更多： $d p [i] [j] = match (s [i - 1], p [j - 2]) && d p [i - 1] [j]$

注意 dp[i-1][j]（j 不减少）表示：消耗掉 s[i-1]，但 a* 还在，可以继续匹配前面的字符。

综合：

$d p [i] [j] = d p [i] [j - 2] (使用 0 次)$ $或 d p [i] [j] = match (s [i - 1], p [j - 2]) && d p [i - 1] [j] (使用 1+ 次)$

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;
 
    // 初始化：空串与模式的匹配（处理 "a*b*c*" 这类能匹配空串的模式）
    for (int j = 2; j <= n; j++) {
        if (p.charAt(j - 1) == '*') {
            dp[0][j] = dp[0][j - 2];  // a* 用0次，等效于去掉 a*
        }
    }
 
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '*') {
                // 情况1：* 用0次（a* 整体不匹配）
                dp[i][j] = dp[i][j - 2];
 
                // 情况2：* 用1+次（s[i-1] 与 a* 中的 a 匹配）
                if (match(s.charAt(i - 1), p.charAt(j - 2))) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j];
                }
            } else {
                // 普通字符或 '.'
                if (match(s.charAt(i - 1), p.charAt(j - 1))) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
    }
    return dp[m][n];
}
 
private boolean match(char sc, char pc) {
    return pc == '.' || sc == pc;
}

2.4 状态转移的直觉理解

dp[i-1][j] 中 j 不减是理解 * 转移的关键：

dp[i][j] 表示 s[1..i] 与 p[1..j] 匹配
当 p[j] 是 *（假设 j 是 1-indexed），且 s[i] 与 p[j-1] 匹配时：
- * “消耗”了 s[i]，但 * 还没用完，可以继续匹配 s[i-1]——这正是 dp[i-1][j]

想象 s = "aaa"，p = "a*"：

dp[3][2]：s[3]='a' 与 p[1]='a' 匹配，* 消耗 s[3]，检查 dp[2][2]
dp[2][2]：同上，检查 dp[1][2]
dp[1][2]：同上，检查 dp[0][2]
dp[0][2]：空串与 "a*"，* 用 0 次，dp[0][0] = true ✓

第 3 章通配符匹配（LeetCode 44）

3.1 题目

LeetCode 44 - Wildcard Matching（困难）

给定字符串 s 和模式串 p，实现通配符匹配。

? 匹配任意单个字符
* 匹配任意字符串（包括空串）

注意：这里的 * 与正则表达式的 * 完全不同！

s = "aa", p = "a"    → false
s = "aa", p = "*"    → true（* 匹配 "aa"）
s = "cb", p = "?a"   → false（? 匹配 c，但 a != b）
s = "adceb", p = "*a*b" → true

3.2 与正则匹配的核心区别

特性	正则 `a*`	通配符 `*`
`*` 的含义	0个或多个 `a`（前驱字符）	任意字符串（包括空串）
`*` 能单独使用吗	不行（`*` 需要前驱字符）	可以
`*` 匹配的字符	只匹配固定字符 `a`	匹配任意字符

3.3 DP 解法

状态：dp[i][j] = s[0..i-1] 与 p[0..j-1] 是否完全匹配。

Base Case：

dp[0][0] = true（空串与空模式匹配）
dp[0][j]：空串与含 * 的模式。如果 p[0..j-1] 全是 *，则 dp[0][j] = true： dp[0][j] = dp[0][j-1] && p[j-1] == '*'

转移方程：

情况一：p[j-1] 是普通字符或 ?：

$d p [i] [j] = match (s [i - 1], p [j - 1]) && d p [i - 1] [j - 1]$

其中 match(a, b) = (a == b || b == '?')。

情况二：p[j-1] == '*'（通配符 * 匹配任意字符串）：

* 匹配空串：dp[i][j] = dp[i][j-1]（* 不消耗 s 中任何字符，只是把 * 去掉）
* 匹配 1 个或多个字符：dp[i][j] = dp[i-1][j]（* 消耗 s[i-1]，* 还留着继续消耗）

$d p [i] [j] = d p [i] [j - 1] (空) 或 d p [i - 1] [j] (匹配 1+ 个)$

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;
 
    // 初始化：连续的 * 可以匹配空串
    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++) {
            if (p.charAt(j - 1) == '*') {
                // * 匹配空串：dp[i][j-1]
                // * 匹配1+字符：dp[i-1][j]
                dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
            } else {
                // 普通字符或 ?
                dp[i][j] = (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?')
                           && dp[i - 1][j - 1];
            }
        }
    }
    return dp[m][n];
}

3.4 正则 `` vs 通配符 `` 的转移对比

类型	`*` 用0次/空	`*` 用1+次
正则 `a*`	`dp[i][j-2]`（消除 `a` 和 `*`）	`dp[i-1][j]`（消耗 `s[i]`，`a*` 留着）
通配符 `*`	`dp[i][j-1]`（消除 `*`）	`dp[i-1][j]`（消耗 `s[i]`，`*` 留着）

两者的”1+次”转移方程完全一样（dp[i-1][j]），差别在”0次/空”的转移：

正则 a*：* 配合 a 整体消除，跳过 2 个模式字符 → dp[i][j-2]
通配符 *：* 单独消除，跳过 1 个模式字符 → dp[i][j-1]

第 4 章字符串 DP 的边界处理技巧

4.1 1-indexed 的好处

两道匹配题都使用了 1-indexed（dp[i][j] 对应 s[0..i-1] 和 p[0..j-1]），这样：

dp[0][0] = true 自然对应”空串与空模式匹配”
不需要在字符串前端手动加哨兵字符
初始化 dp[0][j] 可以统一处理模式的前缀能否匹配空串

相比之下，如果用 0-indexed（dp[i][j] 对应 s[0..i] 和 p[0..j]），需要额外处理”空串”的边界情况，代码更繁琐。

4.2 `dp[i-1][j-1]` 的正确理解

在 1-indexed DP 中，dp[i-1][j-1] 表示”去掉 s 的最后一个字符 s[i-1] 和 p 的最后一个字符 p[j-1] 后的匹配状态”，对应”两个字符精确匹配”的情况。

不要把 dp[i-1][j-1] 理解为”坐标偏移”，而是”字符串和模式串各消耗一个字符”。

4.3 空间压缩

两道匹配题都是”当前行只依赖上一行”的二维 DP，可以压缩为一维。但正则匹配的 dp[i][j] = dp[i-1][j] 依赖同行的 dp[i-1][j]（实际是上一行，在一维数组中就是 dp[j] 更新前的值），可以直接用一维数组从左到右遍历：

// 正则匹配的一维空间优化
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int j = 2; j <= n; j++) {
    if (p.charAt(j - 1) == '*') dp[j] = dp[j - 2];
}
 
for (int i = 1; i <= m; i++) {
    boolean prev = dp[0];  // 保存 dp[i-1][j-1]（左上角）
    dp[0] = false;         // dp[i][0] = false（非空串与空模式不匹配）
    for (int j = 1; j <= n; j++) {
        boolean temp = dp[j];  // 保存 dp[i-1][j]（未更新前的 dp[j]）
        if (p.charAt(j - 1) == '*') {
            dp[j] = dp[j - 2] || (match(s.charAt(i - 1), p.charAt(j - 2)) && dp[j]);
            // dp[j] 此时还是 dp[i-1][j]，即"上一行的 dp[j]"
        } else {
            dp[j] = match(s.charAt(i - 1), p.charAt(j - 1)) && prev;
            // prev 是 dp[i-1][j-1]（左上角，即上一轮保存的 temp）
        }
        prev = temp;
    }
}
return dp[n];

空间压缩的注意事项

压缩一维时，dp[i-1][j-1]（左上角）在遍历到 j 时已经被更新（变成了 dp[i][j-1]），需要用 prev 变量提前保存。这是所有二维转一维 DP 压缩时的通用技巧。

第 5 章高频字符串 DP 题型速查

5.1 LeetCode 5：最长回文子串

解法：中心扩展， $O (n^{2})$ 时间 $O (1)$ 空间
扩展：Manacher 算法可做到 $O (n)$ ，面试不要求掌握

5.2 LeetCode 516：最长回文子序列

解法：区间 DP，dp[i][j] = dp[i+1][j-1] + 2（两端相等）或 max(dp[i+1][j], dp[i][j-1])
注意与 LCS 的关系：longestPalinSubseq(s) = LCS(s, reverse(s))

5.3 LeetCode 647：回文子串计数

解法：中心扩展统计， $O (n^{2})$ 时间 $O (1)$ 空间

5.4 LeetCode 10：正则表达式匹配

解法：DP，核心难点是 * 的两种用法（0次 vs 1+次）
容易错误：dp[i][j-2] vs dp[i][j-1]（正则 vs 通配符）

5.5 LeetCode 44：通配符匹配

解法：DP，* 匹配空 → dp[i][j-1]，匹配1+字符 → dp[i-1][j]

5.6 LeetCode 72：编辑距离（已在第05篇详解）

解法：双序列 DP，三方向转移

5.7 LeetCode 115：不同的子序列（已在第05篇详解）

解法：双序列 DP，不能删 t 的字符

第 6 章回文判断的三种方法对比

方法	时间	空间	适用场景
中心扩展	$O (n^{2})$	$O (1)$	求最长回文子串、统计回文子串数
区间 DP	$O (n^{2})$	$O (n^{2})$	需要复用 `isPalin[i][j]`（如分割问题）
哈希/双指针	$O (n)$ 判断单串	$O (n)$	快速判断整个字符串是否是回文串
Manacher	$O (n)$	$O (n)$	理论最优，面试几乎不要求

面试建议

让你求”最长回文子串”：中心扩展（代码短，复杂度优，面试首选）

让你”统计回文子串数”：中心扩展（同上）

让你做”回文分割”：先用区间 DP 或中心扩展预计算 isPalin[i][j]，再用线性 DP

小结

本文围绕三大主题展开：

回文专题：

子串问题用中心扩展（ $O (1)$ 空间）
子序列问题用区间 DP（dp[i][j] = dp[i+1][j-1] + 2 或取最大）
需要复用回文信息时，预计算 isPalin[i][j]

正则表达式匹配（LeetCode 10）：

a* 整体表示”0个或多个 a”
* 用0次：dp[i][j] = dp[i][j-2]（消除 a* 两字符）
* 用1+次：match(s[i], a) && dp[i-1][j]（消耗 s[i]，a* 保留）

通配符匹配（LeetCode 44）：

* 匹配任意字符串
* 匹配空：dp[i][j-1]
* 匹配1+：dp[i-1][j]

下一篇树形DP与状态压缩DP：树上决策与位运算加速将介绍两种在特殊结构上的 DP 变体——树形 DP（状态从叶子向根合并）和状态压缩 DP（用二进制位表示集合状态）。

汀的知识碎片

文章导航

08 字符串DP进阶：回文子串、正则与通配符匹配

字符串 DP 进阶：回文子串、正则与通配符匹配

摘要

第 1 章回文子串与最长回文子串

1.1 回文子串计数（LeetCode 647）

1.2 中心扩展法： $O (n^{2})$ 时间 $O (1)$ 空间

1.3 区间 DP 法：适合需要复用回文信息的场景

1.4 最长回文子串（LeetCode 5）

1.5 最长回文子序列（LeetCode 516）

第 2 章正则表达式匹配（LeetCode 10）

2.1 题目

2.2 `*` 的语义陷阱

2.3 状态定义与转移

2.4 状态转移的直觉理解

第 3 章通配符匹配（LeetCode 44）

3.1 题目

3.2 与正则匹配的核心区别

3.3 DP 解法

3.4 正则 `` vs 通配符 `` 的转移对比

第 4 章字符串 DP 的边界处理技巧

4.1 1-indexed 的好处

4.2 `dp[i-1][j-1]` 的正确理解

4.3 空间压缩

第 5 章高频字符串 DP 题型速查

5.1 LeetCode 5：最长回文子串

5.2 LeetCode 516：最长回文子序列

5.3 LeetCode 647：回文子串计数

5.4 LeetCode 10：正则表达式匹配

5.5 LeetCode 44：通配符匹配

5.6 LeetCode 72：编辑距离（已在第05篇详解）

5.7 LeetCode 115：不同的子序列（已在第05篇详解）

第 6 章回文判断的三种方法对比

小结

On this page

汀的知识碎片

文章导航

08 字符串DP进阶：回文子串、正则与通配符匹配

字符串 DP 进阶：回文子串、正则与通配符匹配

摘要

第 1 章 回文子串与最长回文子串

1.1 回文子串计数（LeetCode 647）

1.2 中心扩展法：O(n2) 时间 O(1) 空间

1.3 区间 DP 法：适合需要复用回文信息的场景

1.4 最长回文子串（LeetCode 5）

1.5 最长回文子序列（LeetCode 516）

第 2 章 正则表达式匹配（LeetCode 10）

2.1 题目

2.2 * 的语义陷阱

2.3 状态定义与转移

2.4 状态转移的直觉理解

第 3 章 通配符匹配（LeetCode 44）

3.1 题目

3.2 与正则匹配的核心区别

3.3 DP 解法

3.4 正则 * vs 通配符 * 的转移对比

第 4 章 字符串 DP 的边界处理技巧

4.1 1-indexed 的好处

4.2 dp[i-1][j-1] 的正确理解

4.3 空间压缩

第 5 章 高频字符串 DP 题型速查

5.1 LeetCode 5：最长回文子串

5.2 LeetCode 516：最长回文子序列

5.3 LeetCode 647：回文子串计数

5.4 LeetCode 10：正则表达式匹配

5.5 LeetCode 44：通配符匹配

5.6 LeetCode 72：编辑距离（已在第05篇详解）

5.7 LeetCode 115：不同的子序列（已在第05篇详解）

第 6 章 回文判断的三种方法对比

小结

On this page

第 1 章回文子串与最长回文子串

1.2 中心扩展法： $O (n^{2})$ 时间 $O (1)$ 空间

第 2 章正则表达式匹配（LeetCode 10）

2.2 `*` 的语义陷阱

第 3 章通配符匹配（LeetCode 44）

3.4 正则 `` vs 通配符 `` 的转移对比

第 4 章字符串 DP 的边界处理技巧

4.2 `dp[i-1][j-1]` 的正确理解

第 5 章高频字符串 DP 题型速查

第 6 章回文判断的三种方法对比