面试经典算法题81-最长回文子串

LeetCode.5

问题描述：

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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

思路：

以字符串"babad"为例。

1. 初始化状态：
   • 首先创建一个二维数组 dp，其大小为 n x n（n 为字符串长度），并初始化所有元素为 false。
   • 对于长度为 1 的子串，即 dp[i][i]，将对应位置的元素设为 true，因为单个字符肯定是回文串。
2. 状态转移：
   • 接下来从长度为 2 的子串开始，逐步扩展到长度为 n 的子串，计算 dp[i][j] 的值。
   • 对于每个长度为 len 的子串，枚举起始位置 i，计算结束位置 j = i + len - 1。
   • 如果 s[i] == s[j] 且 dp[i+1][j-1] 为 true，则说明去掉头尾两个字符后的子串是回文串，即 dp[i][j] = true。
3. 记录最长回文子串：
   • 在状态转移的过程中，记录下最长的回文子串的起始位置和长度。
   • 每次更新 dp[i][j] 为 true 时，更新起始位置 start = i 和最大长度 maxLen = len。
4. 返回结果：
   • 最后根据记录的起始位置 start 和最大长度 maxLen，使用 substr 方法从原始字符串中取出最长回文子串并返回。

给个表格帮助大家理解：

表格中，对角线上的格子都表示长度为 1 的子串，因为单个字符肯定是回文串，所以都标记为 true。

然后我们开始计算长度为 2 的子串，例如 ba 和 ab，如果两个字符相同，则标记为 true，否则标记为 false。在这个例子中，ba 和 ab 都不是回文串，所以对应的格子都标记为 false。

接着我们计算长度为 3 的子串，例如 bab 和 aba，如果首尾两个字符相同并且去掉首尾字符的子串是回文串，则标记为 true，否则标记为 false。在这个例子中，bab 是回文串，所以对应的格子标记为 true，而 aba 也是回文串，所以对应的格子也标记为 true。

最后我们计算长度为 4 的子串，例如 baba，同样地，如果首尾两个字符相同并且去掉首尾字符的子串是回文串，则标记为 true，否则标记为 false。在这个例子中，baba 不是回文串，所以对应的格子标记为 false。

最终，我们可以根据这个表格得到最长的回文子串是 "bab"。

参考代码：

C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

string longestPalindrome(string s) {
    if (s.empty()) return "";
    int n = s.length();
    vector<vector<bool>> dp(n, vector<bool>(n, false));  // 定义二维动态规划数组
    int start = 0, maxLen = 1;  // 记录最长回文子串的起始位置和长度
    for (int i = 0; i < n; ++i) {
        dp[i][i] = true;  // 单个字符肯定是回文串
        if (i < n - 1 && s[i] == s[i + 1]) {
            dp[i][i + 1] = true;  // 相邻字符相同则是回文串
            start = i;
            maxLen = 2;
        }
    }
    for (int len = 3; len <= n; ++len) {  // 枚举子串长度
        for (int i = 0; i + len - 1 < n; ++i) {  // 枚举子串起始位置
            int j = i + len - 1;  // 子串结束位置
            if (s[i] == s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;  // 根据状态转移方程计算 dp[i][j]
                start = i;
                maxLen = len;
            }
        }
    }
    return s.substr(start, maxLen);  // 返回最长回文子串
}

int main() {
    string s = " ";
    std::cout << "输入字符串：";
    std::cin >> s;
    std::cout << longestPalindrome(s) << std::endl;  // 输出最长回文子串
    return 0;
}

Java

public class LongestPalindrome {
    
    public static String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        int n = s.length();
        boolean[][] dp = new boolean[n][n];  // 定义二维动态规划数组
        int start = 0, maxLen = 1;  // 记录最长回文子串的起始位置和长度
        
        for (int i = 0; i < n; ++i) {
            dp[i][i] = true;  // 单个字符肯定是回文串
            if (i < n - 1 && s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;  // 相邻字符相同则是回文串
                start = i;
                maxLen = 2;
            }
        }
        
        for (int len = 3; len <= n; ++len) {  // 枚举子串长度
            for (int i = 0; i + len - 1 < n; ++i) {  // 枚举子串起始位置
                int j = i + len - 1;  // 子串结束位置
                if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                    dp[i][j] = true;  // 根据状态转移方程计算 dp[i][j]
                    start = i;
                    maxLen = len;
                }
            }
        }
        return s.substring(start, start + maxLen);  // 返回最长回文子串
    }

    public static void main(String[] args) {
        java.util.Scanner scanner = new java.util.Scanner(System.in);
        System.out.println("请输入字符串：");
        String s = scanner.nextLine();
        System.out.println("最长回文子串为：" + longestPalindrome(s));
        scanner.close();
    }
}

Python

def longestPalindrome(s: str) -> str:
    if not s:
        return ""
    
    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 = i
            max_len = 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  # 根据状态转移方程计算 dp[i][j]
                start = i
                max_len = length

    return s[start:start + max_len]  # 返回最长回文子串

# 主函数用于测试
if __name__ == "__main__":
    s = input("输入字符串：")
    print("最长回文子串为：", longestPalindrome(s))