题目

对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。

数据范围：1≤n≤1000

要求：空间复杂度 O(1)，时间复杂度 O(n2)

进阶:  空间复杂度 O(n)，时间复杂度 O(n)

示例1

输入：

"ababc"

返回值：

3

说明：

最长的回文子串为"aba"与"bab"，长度都为3

示例2

输入：

"abbba"

返回值：

5

示例3

输入：

"b"

返回值：

1

---

代码

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可* @param A string字符串* @return int整型*/public int getLongestPalindrome (String A) {//1.创建dp表//2.初始化int n = A.length();boolean[][] dp = new boolean[n][n];//3.填表int len = 1; //记录最长子串的长度for (int i = n - 1; i >= 0; i--) {for (int j = i; j < n; j++) {if (A.charAt(i) == A.charAt(j)) {dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;}if (dp[i][j] && j - i + 1 > len) {len = j - i + 1;}}}//4.返回值return len;}
}