题解 | #编号子回文I#

知识点：动态规划

思路：

首先，创建一个二维布尔数组f，f[i][j]表示字符串从第i个字符到第j个字符的子串是否为回文串。初始化对角线上的元素为true，表示单个字符都是回文串。

然后，使用两重循环遍历字符串s，从长度为2的子串开始，逐步增加长度。对于每个长度len，我们遍历字符串s的每个起始位置i，并计算对应的结束位置j。如果s[i]与s[j]相等，并且子串s[i+1][j-1]也是回文串（或者子串长度为1），则将f[i][j]设为true，并更新最长回文子串res。

最终，res即为给定字符串s中的最长回文子串。

编程语言：java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return string字符串
     */
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] f = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            f[i][i] = true;
        }
        String res = "";
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    if (j == i + 1 || f[i + 1][j - 1]) {
                        f[i][j] = true;
                        res = s.substring(i, i + len);
                    }
                }
            }
        }
        return res;
    }
}