怎么用Java找到最长回文子串

问题背景

最长回文子串指的是一个字符串中的连续字符序列，该序列从前往后读和从后往前读是一样的。例如，字符串"abcbad"的最长回文子串是"abcba"。

本文将介绍使用Java语言解决这个问题的方法。其中，我们将使用动态规划算法，该算法在解决最长回文子串问题时具有较好的时间复杂度。

动态规划算法

动态规划算法的基本思想是将一个复杂问题分解为若干个子问题，并通过记录和利用已解决的子问题的结果来求解整个问题。

在求解最长回文子串的问题中，我们可以使用一个二维数组dp[i][j]来表示子串s[i...j]是否为回文串。其中，dp[i][j]的值为true表示s[i...j]是一个回文串，否则为false。

求解过程

1. 初始化dp数组，将对角线上的元素和相邻元素（长度为1和2的子串）设为true。

2. 根据子串长度递增的顺序，遍历所有可能的子串长度，更新dp数组。对于长度大于2的子串s[i...j]，如果s[i]和s[j]相等，并且s[i+1...j-1]也是回文串，则s[i...j]也是回文串（即dp[i][j]=true），否则不是。

3. 在更新dp数组的过程中，记录最长的回文子串的长度和起始位置，即维护两个变量start和maxLength。若dp[i][j]为true且j-i+1大于maxLength，则更新start和maxLength的值。

4. 根据得到的最长回文子串的起始位置和长度，即可得到最长回文子串。

public static String longestPalindrome(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    int start = 0;
    int maxLength = 1;
    
    // 初始化dp数组
    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;
            maxLength = 2;
        }
    }
    
    // 更新dp数组
    for (int len = 3; len <= n; len++) {
        for (int i = 0; i < n - len + 1; i++) {
            int j = i + len - 1;
            if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                if (len > maxLength) {
                    start = i;
                    maxLength = len;
                }
            }
        }
    }
    
    // 获取最长回文子串
    return s.substring(start, start + maxLength);
}