DSA Interview Prep · 课时

最长回文子序列与子串

Q: 「最长回文子序列与子串」这节课中我会学到什么？

应用区间 DP 查找最长回文子序列，并使用从中心向外扩展的技巧查找最长回文子串。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

应用区间 DP 查找最长回文子序列，并使用从中心向外扩展的技巧查找最长回文子串。

最长回文子序列与子串 是 CoddyKit 上的免费 DSA Interview Prep 课时。这是第 2 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。

重新认识回文定义

回文子序列是指从正向和反向读取都相同的子序列（元素不一定连续）。回文子串则要求字符连续。对于 'bbbab'，最长回文子序列是 'bbbb'（长度为 4），而最长回文子串是 'bbb'（长度为 3）。尽管名称相似，这两个问题需要使用不同的技术。

最长回文子序列：LPS 状态

将 dp[i][j] 定义为 s[i..j] 中最长回文子序列的长度。递推关系为：如果 s[i] == s[j]，那么 dp[i][j] = dp[i+1][j-1] + 2（两个匹配的字符会扩展内部回文）。否则，dp[i][j] = max(dp[i+1][j], dp[i][j-1])（跳过左侧或右侧字符）。基础情况是：对于所有单个字符，dp[i][i] = 1。

s = 'bbbab'
n = len(s)
dp = [[0]*n for _ in range(n)]
for i in range(n):
    dp[i][i] = 1
print('Base cases set, dp[i][i] = 1 for all i')

LPS 填充顺序与实现

我们按照区间长度递增的顺序填充 LPS 表，这与一般的区间 DP 模式相同。对于长度为 2 或更长的每个区间 [i, j]，我们检查两个边界字符是否匹配，然后应用递推关系。最终答案是 dp[0][n-1]，即整个字符串的 LPS。

def longest_palindromic_subsequence(s):
    n = len(s)
    dp = [[0]*n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1
    
    for length in range(2, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                inner = dp[i+1][j-1] if length > 2 else 0
                dp[i][j] = inner + 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    return dp[0][n-1]

print(longest_palindromic_subsequence('bbbab'))  # 4

通过 LCS 得到 LPS 的等价方法

一种优雅的替代方法是：字符串 s 的 LPS 等于 s 与其反转字符串 s[::-1] 的 LCS。这是因为 s 的任何回文子序列都是 s 及其反转字符串的公共子序列。通过这种转换，您可以直接复用 LCS 代码。'bbbab' 反转后为 'babbb'，它们的 LCS 长度为 4。

def lps_via_lcs(s):
    t = s[::-1]
    m, n = len(s), len(t)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s[i-1] == t[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

print(lps_via_lcs('bbbab'))  # 4

最长回文子串：暴力法

最长回文子串要求字符连续。暴力方法会检查全部 O(n²) 个子串，并在 O(n) time 内验证每个子串，因此总复杂度为 O(n³)。有两种更快的方法：O(n²) time 和空间的区间 DP，以及O(n²) time 但仅使用 O(1) 空间的围绕中心扩展。在面试中，通常更推荐围绕中心扩展，因为它的常数更小，代码也更简洁。

回文子串的区间 DP

定义当 s[i..j] 是回文时 dp[i][j] = True。递推关系为：dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]。基础情况为：dp[i][i] = True，以及 dp[i][i+1] = (s[i] == s[i+1])。记录找到的最长回文长度。按照长度递增的顺序填充。该方法的 time 复杂度为 O(n²)，空间复杂度为 O(n²)。

def longest_palindrome_dp(s):
    n = len(s)
    dp = [[False]*n for _ in range(n)]
    start, max_len = 0, 1
    for i in range(n):
        dp[i][i] = True
    for i in range(n-1):
        if s[i] == s[i+1]:
            dp[i][i+1] = True
            start, max_len = i, 2
    for length in range(3, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and dp[i+1][j-1]:
                dp[i][j] = True
                if length > max_len:
                    start, max_len = i, length
    return s[start:start+max_len]

print(longest_palindrome_dp('babad'))  # 'bab' or 'aba'

围绕中心扩展技术

围绕中心扩展方法将每个字符（以及每一对相邻字符）作为潜在的回文中心，并在两侧匹配时不断向外扩展。共有 2n-1 个可能的中心（n 个奇数长度中心，n-1 个偶数长度中心）。每次扩展最多需要 O(n) time，因此总复杂度为 O(n²)，空间复杂度为 O(1)——这对于大多数面试场景来说是最优的。

def longest_palindrome_expand(s):
    def expand(l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        return r - l - 1  # length of palindrome
    
    start, max_len = 0, 1
    for i in range(len(s)):
        odd = expand(i, i)      # odd-length
        even = expand(i, i+1)   # even-length
        best = max(odd, even)
        if best > max_len:
            max_len = best
            start = i - (best - 1) // 2
    return s[start:start+max_len]

print(longest_palindrome_expand('cbbd'))  # 'bb'

LPS 空间优化

LPS 区间 DP 使用 O(n²) 空间。当您只需要长度而不需要实际的子序列时，可以注意到 dp[i][j] 只依赖于 dp[i+1][j-1]、dp[i+1][j] 和 dp[i][j-1]，从而减少空间使用。通过复用行并保存一个对角线值，可以达到 O(n) 空间——不过实现会更加复杂，面试中很少要求这样做。

重建 LPS

要重建实际的回文子序列，请沿 DP 表回溯。从 (0, n-1) 开始。如果 s[i] == s[j]，就将该字符添加到结果的两端，然后移动到 (i+1, j-1)。否则，移动到 (i+1, j) 和 (i, j-1) 中数值较大的位置。这种贪心式回溯可以唯一地恢复出一个最优回文子序列。

def reconstruct_lps(s, dp):
    result = []
    i, j = 0, len(s) - 1
    while i < j:
        if s[i] == s[j]:
            result.append(s[i])
            i += 1; j -= 1
        elif dp[i+1][j] > dp[i][j-1]:
            i += 1
        else:
            j -= 1
    # middle character for odd-length
    mid = [s[i]] if i == j else []
    return ''.join(result + mid + result[::-1])

print('Traceback recovers one optimal LPS')

比较 LPS 与 LCS 的 time 复杂度

通过区间 DP 求 LPS 和求 LCS 的复杂度都是O(n²) time 和 O(n²) 空间。求最长回文子串的围绕中心扩展方法为 O(n²) time，但只使用 O(1) 空间。Manacher 算法可以在 O(n) time 和空间内解决子串问题，但它的复杂程度较高，面试官很少要求掌握它。对于大多数面试场景，围绕中心扩展是子串变体所期望的最优 solution。

常见陷阱与边界情况

请注意以下陷阱：(1) 混淆子序列和子串——这是两个不同的问题，需要不同的解决方案；(2) 长度为 2 的区间的区间 DP 基础情况需要特殊处理，因为 dp[i+1][j-1] 会变成 dp[i+1][i]（空区间）；(3) 对于中心扩展，请将 max_len = 1 初始化（每个单字符都是回文）；(4) 提取结果时，计算 start = i - (best-1)//2，以便根据中心正确找到起始索引。

快速检查

测试您对本课数据结构 & 算法 — 编程面试准备相关概念的理解。

课程回顾

在本课中，您学到了：LPS 使用区间 DP，其递推关系为 dp[i][j] = dp[i+1][j-1]+2（字符匹配时）；最长回文子串最好使用中心扩展解决，时间复杂度为 O(n²)，空间复杂度为 O(1)；以及LPS 等于字符串与其反转字符串的 LCS。接下来我们将学习回文分割 II，它将回文表与用于求最少切分次数的一维 DP 相结合。

常见问题解答

「最长回文子序列与子串」课时是免费的吗？

是的 — 「最长回文子序列与子串」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。

「最长回文子序列与子串」这节课中我会学到什么？

应用区间 DP 查找最长回文子序列，并使用从中心向外扩展的技巧查找最长回文子串。你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 DSA Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。这是第 2 节课，共 4 节。

「最长回文子序列与子串」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 DSA Interview Prep 课中编写并运行代码吗？

能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

← 返回 DSA Interview Prep