解题思路：动态规划

• 使用 dp[i][j] 记录 s[i:j+1] 是否是回文子串。
• 递推关系：
  • 如果 s[i] == s[j]：
    • j - i == 1，即两个字符相等，则是回文。
    • dp[i+1][j-1] == True（内部是回文），则 dp[i][j] = True。
• 遍历 j 作为子串右端点，从小到大枚举 i 作为左端点，更新 dp[i][j] 并记录最长回文子串的起始位置 start 和长度 max_length。
• 时间复杂度 O(n²)，空间复杂度 O(n²)。

Python 代码

import sys

def longest_palindrome_dp(s):
    """ 使用动态规划找到最长回文子串 """
    n = len(s)
    if n == 0:
        return ""

    # 初始化 DP 数组，dp[i][j] 表示 s[i:j+1] 是否是回文
    dp = [[False] * n for _ in range(n)]
    start, max_length = 0, 1  # 记录最长回文子串的起始索引和长度

    # 所有单个字符都是回文
    for i in range(n):
        dp[i][i] = True

    # 处理长度大于 1 的子串
    for length in range(2, n + 1):  # 从长度 2 开始遍历
        for i in range(n - length + 1):  # 遍历起始索引
            j = i + length - 1  # 计算子串的结束索引
            if s[i] == s[j]:  # 首尾字符相等
                if length == 2 or dp[i + 1][j - 1]:  # 两个字符或内部是回文
                    dp[i][j] = True
                    if length > max_length:  # 更新最长回文
                        start = i
                        max_length = length

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

def main():
    """ 读取输入并调用求解函数 """
    s = sys.stdin.readline().strip()  # 读取输入字符串
    print(longest_palindrome_dp(s))  # 输出最长回文子串

if __name__ == "__main__":
    main()

Java 代码

import java.util.*;

public class Main {
    public static String longestPalindromeDP(String s) {
        int n = s.length();
        if (n == 0) return "";

        // 初始化 DP 数组
        boolean[][] dp = new boolean[n][n];
        int start = 0, maxLength = 1; // 记录最长回文子串的起始索引和长度

        // 所有单个字符都是回文
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        // 处理长度大于 1 的子串
        for (int length = 2; length <= n; length++) {  // 子串长度从 2 开始
            for (int i = 0; i <= n - length; i++) {  // 遍历起始索引
                int j = i + length - 1;  // 计算子串的结束索引
                if (s.charAt(i) == s.charAt(j)) {  // 首尾字符相等
                    if (length == 2 || dp[i + 1][j - 1]) {  // 两个字符或内部是回文
                        dp[i][j] = true;
                        if (length > maxLength) {  // 更新最长回文
                            start = i;
                            maxLength = length;
                        }
                    }
                }
            }
        }
        return s.substring(start, start + maxLength);  // 返回最长回文子串
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();  // 读取输入字符串
        System.out.println(longestPalindromeDP(s));  // 输出最长回文子串
        sc.close();
    }
}

C++ 代码

#include <iostream>
#include <vector>
#include <string>

using namespace std;

string longestPalindromeDP(string s) {
    int n = s.size();
    if (n == 0) return "";

    // 初始化 DP 数组
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    int start = 0, maxLength = 1;  // 记录最长回文子串的起始索引和长度

    // 所有单个字符都是回文
    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
    }

    // 处理长度大于 1 的子串
    for (int length = 2; length <= n; length++) {  // 子串长度从 2 开始
        for (int i = 0; i <= n - length; i++) {  // 遍历起始索引
            int j = i + length - 1;  // 计算子串的结束索引
            if (s[i] == s[j]) {  // 首尾字符相等
                if (length == 2 || dp[i + 1][j - 1]) {  // 两个字符或内部是回文
                    dp[i][j] = true;
                    if (length > maxLength) {  // 更新最长回文
                        start = i;
                        maxLength = length;
                    }
                }
            }
        }
    }
    return s.substr(start, maxLength);  // 返回最长回文子串
}

int main() {
    string s;
    cin >> s;  // 读取输入字符串
    cout << longestPalindromeDP(s) << endl;  // 输出最长回文子串
    return 0;
}

Leetcode 93.最长回文子串-原题链接

题目描述

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

输入描述

输入包含一个字符串 s（$1 \leq |s| \leq 1000$），仅由数字和英文字母组成。

输出描述

输出一行，表示 s 中最长的回文子串。如果存在多个答案，返回任意一个。

样例输入 1

babad

样例输出 1

bab

说明：aba 也是符合题意的答案。

样例输入 2

cbbd

样例输出 2

bb

提示

• s 仅由 数字 和 英文字母 组成。
• s 至少包含 1 个字符。
• 若存在多个答案，返回 任意一个。