题解 | #编号子回文I#

知识点

动态规划

解题思路

使用一个二维数组dp来保存状态转移矩阵，其中dp[i][j]表示从索引i到j的子串是否是回文串。

首先，我们初始化状态，将单个字符视为回文串，即dp[i][j]=true。

然后，我们使用两个嵌套循环遍历所有的子串，根据首尾字符是否相同，并且中间部分是否回文串来判断整个子串是否为回文串。如果是回文串，则更新最长回文串的长度和起始位置。

最终，我们通过substring方法返回最长回文串的子串。

Java题解

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return string字符串
     */
    public String longestPalindrome (String s) {
        // write code here
        int n = s.length();

        // 创建一个二维数组来存储状态转移矩阵
        boolean[][] dp = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        int maxLength = 1; // 记录最长回文串的长度
        int start = 0; // 记录最长回文串的起始位置

        for (int j = 1; j < n; j++) {
            for (int i = 0; i < j; i++) {
                // 如果首尾字符相同，并且中间部分是回文串，则整个字符串是回文串
                if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;

                    // 更新最长回文串的长度和起始位置
                    if (j - i + 1 > maxLength) {
                        maxLength = j - i + 1;
                        start = i;
                    }
                }
            }
        }

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