题解 | #编号子回文I#

一、知识点：

循环、遍历、回文字

二、文字分析：

定义一个二维数组dp，其中dp[i][j]表示从字符串s的第i个字符到第j个字符的子串是否是回文串。

状态转移方程为：

dp[i][j] = dp[i+1][j-1] && s.charAt(i) == s.charAt(j)

其中i < j。

初始化：

• 对于长度为1的子串，dp[i][i]的初始值都为true。
• 对于长度为2的子串，如果s.charAt(i) == s.charAt(j)，则dp[i][j]的初始值为true，否则为false。

维护一个变量maxLength来记录最长回文串的长度以及起始位置，初始化为0。

遍历字符串s的所有子串，根据状态转移方程更新dp数组，并更新maxLength的值。

最终结果为通过maxLength找到的最长回文串。

时间复杂度：

• 使用两层循环遍历字符串所有可能的子串，时间复杂度为O(n^2)。
• 在每个子串的比对过程中，需要常数时间来比较字符，时间复杂度为O(1)。

因此，算法的总体时间复杂度为O(n^2)。

空间复杂度：

• 需要一个二维数组dp来保存每个子串是否是回文串的状态，空间复杂度为O(n^2)。
• 需要常数空间来保存最长回文串的长度和起始位置，空间复杂度为O(1)。

所以，算法的总体空间复杂度为O(n^2)。

三、编程语言：

java

四、正确代码：

import java.util.*;


public class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n < 2) return s;

        boolean[][] dp = new boolean[n][n];

        int maxLength = 1;
        int start = 0;

        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        for (int i = 0; i < n - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
                start = i;
                maxLength = 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;
                    start = i;
                    maxLength = len;
                }
            }
        }

        return s.substring(start, start + maxLength);
    }
}