动态规划8：回文子串问题

引言

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

今天我们将探讨动态规划中又一个经典的字符串问题——回文子串问题。回文字符串具有独特的对称性质，在文本处理、密码学、生物信息学等领域都有重要应用。通过学习这个问题，我们将掌握多种不同的算法思想和优化技巧。

问题定义

什么是回文字符串？

回文字符串：正读和反读都相同的字符串。

例如：

• 单个字符："a"、"b"（都是回文）
• 对称字符串："aba"、"abcba"
• 偶数长度："abba"、"aa"

经典例题

我们将围绕以下几个经典问题展开讨论：

1. LeetCode 5. 最长回文子串
2. LeetCode 647. 回文子串
3. LeetCode 516. 最长回文子序列

问题一：最长回文子串

问题描述

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 也是一个有效答案。

示例 2：
输入：s = "cbbd"
输出："bb"

解法一：暴力枚举

思路：枚举所有可能的子串，检查是否为回文。

public String longestPalindrome(String s) {
    if (s == null || s.length() < 2) {
        return s;
    }
    
    int start = 0, maxLen = 1;
    
    for (int i = 0; i < s.length(); i++) {
        for (int j = i + 1; j < s.length(); j++) {
            if (isPalindrome(s, i, j) && j - i + 1 > maxLen) {
                start = i;
                maxLen = j - i + 1;
            }
        }
    }
    
    return s.substring(start, start + maxLen);
}

private boolean isPalindrome(String s, int left, int right) {
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

时间复杂度：O(n³)，空间复杂度：O(1)

解法二：动态规划

状态定义

定义 dp[i][j] 表示：字符串 s[i...j] 是否为回文子串。

状态转移方程

如果 s[i] == s[j]：
    如果 j - i <= 2：dp[i][j] = true     // 长度为1,2,3的情况
    否则：dp[i][j] = dp[i+1][j-1]        // 依赖内部子串
否则：
    dp[i][j] = false

代码实现

public String longestPalindrome(String s) {
    int n = s.length();
    if (n < 2) return s;
    
    boolean[][] dp = new boolean[n][n];
    int start = 0, maxLen = 1;
    
    // 初始化：所有长度为1的子串都是回文
    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
    }
    
    // 检查长度为2的子串
    for (int i = 0; i < n - 1; i++) {
        if (s.charAt(i) == s.charAt(i + 1)) {
            dp[i][i + 1] = true;
            start = i;
            maxLen = 2;
        }
    }
    
    // 检查长度大于2的子串
    for (int len = 3; 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 + 1][j - 1]) {
                dp[i][j] = true;
                start = i;
                maxLen = len;
            }
        }
    }
    
    return s.substring(start, start + maxLen);
}

时间复杂度：O(n²)，空间复杂度：O(n²)

解法三：中心扩展

核心思想：回文串一定有一个中心，从中心向两边扩展检查。

public String longestPalindrome(String s) {
    if (s == null || s.length() < 2) {
        return s;
    }
    
    int start = 0, maxLen = 1;
    
    for (int i = 0; i < s.length(); i++) {
        // 奇数长度回文：以i为中心
        int len1 = expandAroundCenter(s, i, i);
        // 偶数长度回文：以i和i+1为中心
        int len2 = expandAroundCenter(s, i, i + 1);
        
        int len = Math.max(len1, len2);
        if (len > maxLen) {
            maxLen = len;
            start = i - (len - 1) / 2;
        }
    }
    
    return s.substring(start, start + maxLen);
}

private int expandAroundCenter(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return right - left - 1;
}

时间复杂度：O(n²)，空间复杂度：O(1)

解法四：Manacher算法

Manacher算法是专门解决回文问题的线性时间算法。

预处理

在每个字符间插入特殊字符（如’#’），统一处理奇偶长度：

• "babad" → "#b#a#b#a#d#"

核心思想

利用回文的对称性质，避免重复计算。

public String longestPalindrome(String s) {
    if (s == null || s.length() == 0) return "";
    
    // 预处理字符串
    String processed = preprocess(s);
    int n = processed.length();
    int[] P = new int[n]; // P[i]表示以i为中心的回文半径
    int center = 0, right = 0;
    
    for (int i = 0; i < n; i++) {
        // 利用对称性质初始化
        int mirror = 2 * center - i;
        if (i < right) {
            P[i] = Math.min(right - i, P[mirror]);
        }
        
        // 尝试扩展
        try {
            while (processed.charAt(i + P[i] + 1) == processed.charAt(i - P[i] - 1)) {
                P[i]++;
            }
        } catch (StringIndexOutOfBoundsException e) {
            // 边界处理
        }
        
        // 更新center和right
        if (i + P[i] > right) {
            center = i;
            right = i + P[i];
        }
    }
    
    // 找到最长回文
    int maxLen = 0, centerIndex = 0;
    for (int i = 0; i < n; i++) {
        if (P[i] > maxLen) {
            maxLen = P[i];
            centerIndex = i;
        }
    }
    
    int start = (centerIndex - maxLen) / 2;
    return s.substring(start, start + maxLen);
}

private String preprocess(String s) {
    StringBuilder sb = new StringBuilder();
    for (char c : s.toCharArray()) {
        sb.append('#').append(c);
    }
    sb.append('#');
    return sb.toString();
}

时间复杂度：O(n)，空间复杂度：O(n)

问题二：回文子串计数

问题描述（计数问题）

LeetCode 647. 回文子串

给你一个字符串 s，请你统计并返回这个字符串中回文子串的数目。

示例 1：
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

解法一：动态规划

public int countSubstrings(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    int count = 0;
    
    // 长度为1
    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
        count++;
    }
    
    // 长度为2
    for (int i = 0; i < n - 1; i++) {
        if (s.charAt(i) == s.charAt(i + 1)) {
            dp[i][i + 1] = true;
            count++;
        }
    }
    
    // 长度大于2
    for (int len = 3; 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 + 1][j - 1]) {
                dp[i][j] = true;
                count++;
            }
        }
    }
    
    return count;
}

解法二：中心扩展

public int countSubstrings(String s) {
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
        // 奇数长度
        count += expandAroundCenter(s, i, i);
        // 偶数长度
        count += expandAroundCenter(s, i, i + 1);
    }
    return count;
}

private int expandAroundCenter(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;
}

问题三：最长回文子序列

问题描述（子序列问题）

LeetCode 516. 最长回文子序列

给你一个字符串 s，找出其中最长的回文子序列，并返回该序列的长度。

示例：
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb"

区分子串和子序列

• 子串（substring）：连续的字符序列
• 子序列（subsequence）：保持相对顺序但不要求连续的字符序列

动态规划解法

状态定义（子序列）

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])

代码实现（子序列）

public int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    
    // 初始化：单个字符的回文长度为1
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }
    
    // 按长度从小到大填充
    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];
}

时间复杂度：O(n²)，空间复杂度：O(n²)

算法对比分析

问题类型	暴力法	动态规划	中心扩展	Manacher
最长回文子串	O(n³)	O(n²)	O(n²)	O(n)
回文子串计数	O(n³)	O(n²)	O(n²)	O(n)
最长回文子序列	-	O(n²)	-	-

优化技巧总结

1. 空间优化

对于回文子序列问题，可以将二维DP优化为一维：

public int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[] dp = new int[n];
    
    for (int i = n - 1; i >= 0; i--) {
        dp[i] = 1;
        int pre = 0;
        for (int j = i + 1; j < n; j++) {
            int temp = dp[j];
            if (s.charAt(i) == s.charAt(j)) {
                dp[j] = pre + 2;
            } else {
                dp[j] = Math.max(dp[j], dp[j - 1]);
            }
            pre = temp;
        }
    }
    
    return dp[n - 1];
}

2. 边界处理技巧

在实现时要注意：

• 空字符串和单字符的特殊情况
• 数组越界的边界检查
• 奇偶长度回文的统一处理

3. 算法选择建议

• 小数据量：暴力法简单易懂
• 中等数据量：动态规划或中心扩展
• 大数据量：Manacher算法
• 子序列问题：只能用动态规划

实际应用场景

1. DNA序列分析

在生物信息学中，回文序列常出现在DNA的限制性内切酶识别位点。

2. 密码学

某些加密算法利用回文性质进行数据验证。

3. 文本处理

• 检测文本中的对称模式
• 诗歌韵律分析
• 回文诗的创作辅助

4. 数据结构验证

检查字符串、数组等数据结构的对称性。

扩展问题

1. 分割回文串

LeetCode 131. 分割回文串

将字符串分割成若干个回文子串。

2. 最短回文串

LeetCode 214. 最短回文串

通过在字符串前面添加字符使其成为回文串。

3. 回文对

LeetCode 336. 回文对

找出字符串数组中能组成回文串的索引对。

总结

回文子串问题展现了算法设计的多样性和优化的层次性：

1. 算法思想递进

从暴力枚举到动态规划，再到中心扩展和Manacher算法，体现了算法优化的思路。

2. 问题变形丰富

子串、子序列、计数、分割等不同变形，锻炼了我们的问题抽象能力。

3. 实用价值高

在文本处理、生物信息学等领域都有实际应用。

4. 优化空间大

从O(n³)到O(n)的时间复杂度优化，从O(n²)到O(1)的空间优化。

通过学习回文子串问题，我们不仅掌握了具体的算法技巧，更重要的是理解了如何从不同角度思考问题，如何利用数据的特性进行算法优化。

系列文章回顾

• 动态规划入门：从爬楼梯问题开始
• 动态规划进阶：最长公共子序列问题
• 动态规划深入：01背包问题详解
• 动态规划4：最长递增子序列问题
• 动态规划5：不同路径问题与路径计数
• 动态规划6：股票买卖问题
• 动态规划7：编辑距离问题

推荐练习

• 在LeetCode上练习更多回文相关的题目
• 尝试实现Manacher算法的完整版本
• 思考回文问题的其他优化方法
• 研究KMP算法与回文检测的关系