描述
对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。
方法1：奇数偶数分别从中心扩展
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param A string字符串
* @return int整型
*/
public int getLongestPalindrome (String A) {
int n = A.length();
int maxLen = Integer.MIN_VALUE;
for(int i = 0; i < n; i++) {
maxLen = Math.max(maxLen, getLen(i, i + 1, A));
maxLen = Math.max(maxLen, getLen(i - 1, i + 1, A));
}
return maxLen;
}
public static int getLen(int l, int r, String A) {
while(l >= 0 && r <= A.length() - 1 && A.charAt(l) == A.charAt(r)) {
l--;
r++;
}
return r - l - 1;
}
}
方法2：动态规划【未做出来】
public class Solution {
public int getLongestPalindrome(String A) {
if (A.length()<=1) return A.length();
int n = A.length();
int[][] dp = new int[n][n];
int res = 1;
int len = A.length();
// 长度为 1 的串，肯定是回文的
for (int i = 0; i < n; i++) {
dp[i][i]=1;
}
// 将长度为 2-str.length 的所有串遍历一遍
for (int step = 2; step <= A.length(); step++) {
for (int l = 0; l < A.length(); l++) {
int r=l+step-1;
if (r>=len) break;
if (A.charAt(l)==A.charAt(r)) {
if (r-l==1) dp[l][r]=2;
else dp[l][r]=dp[l+1][r-1]==0?0:dp[l+1][r-1]+2;
}
res=Math.max(res,dp[l][r]);
}
}
return res;
}
}
