- 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。
示例 2：
输入：s = “cbbd”
输出：“bb”
示例 3：
输入：s = “a”
输出：“a”
示例 4：
输入：s = “ac”
输出：“a”
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成
动态规划和中心扩展法实现：
public class LongestPalindrome {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("请输入一个字符串：");
String s = scanner.nextLine();
String s1 = longestPalindrome(s);
String s2 = longestPalindrome2(s);
System.out.println("中心扩展法最长回文子串："+s1);
System.out.println("动态规划法最长回文子串："+s2);
}
//动态规划算法
private static String longestPalindrome2(String s) {
int len = s.length();
if (len<2){
return s;
}
int maxLen = 1;
int begin = 0;
//dp[i][j]表示s[i,,,,j]子串，是否是回文字符串
boolean [][]dp = new boolean[len][len];
//初始化dp，所有长度为1的子串都是回文串
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}
char[] array = s.toCharArray();
//递推，枚举子串长度
for (int l = 2; l <= len ; l++) {
for (int i = 0; i < len; i++) {
//由长度和起始位置推出结束位置：j-i+1=l
int j = l+i-1;
if (j>=len){
break;
}
if (array[i]!= array[j]){
dp[i][j] = false;
}else{
if (l<4){
dp[i][j] = true;
}else{
dp[i][j] = dp[i+1][j-1];
}
}
//只要dp[i][j]为true表明s[i,,,,j]是回文串，记录长度和起始位置
if (dp[i][j] == true &&j-i+1>maxLen){
maxLen = j-i+1;
begin = i;
}
}
}
return s.substring(begin,begin+maxLen);
}
//中心扩展算法
private static String longestPalindrome(String s) {
if (s == null|| s.length()<1){
return "";
}
int start = 0,end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandArroundCenter(s,i,i);//子串为奇数
int len2 = expandArroundCenter(s,i,i+1);//子串为偶数
int maxlen = Math.max(len1,len2);
if (maxlen > end-start){
start = i-(maxlen-1)/2;
end = i+maxlen/2;
}
}
return s.substring(start,end+1);
}
private static int expandArroundCenter(String s, int left, int right) {
while (left>=0&&right
