最长回文子串

1.暴力解法
提出出字符串的每一个子字符串，判断是否为回文串，如果是的话，就记录下值，要最大的那一个。时间复杂度为：O（n2），两次循环；空间复杂度为：O（1）。
import java.util.*;

public class Solution {
public int getLongestPalindrome(String A, int n) {
// write code here
if(n==0||n==1)
return n;
int res=0;
for(int i=0;i<n;i++){
for(int j=i+1;j<=n;j++){
String s=A.substring(i,j);//提取出A的子字符串
if(isPalindrome(s))
res=Math.max(res,s.length());
}
}
return res;
}
public boolean isPalindrome(String A){//判断是否为回文串
int len=A.length();
for(int i=0;i<len/2;i++){
if(A.charAt(i)!=A.charAt(len-i-1))//左右字符不同
return false;
}
return true;
}
}
只会暴力解法，看了大佬的思路：
2.中心扩散法
类似于aba，abba这种可以从中间开始进行比较，以一个字符或者两个字符为中心，向左右两边进行扩散比较，最后取得回文子串的最大长度。时间复杂度：O（n2），选中心点一次循环，向左右扩散一次循环。空间复杂度：O（1）
import java.util.*;

public class Solution {
public int getLongestPalindrome(String A, int n) {
// write code here
if(n==0||n==1)
return n;
int res=0;
for(int i=0;i<n;i++){
//一个或两个字符当做中心
int temp=Math.max(centralDiffusion(A,i,i),centralDiffusion(A,i,i+1));
res=Math.max(res,temp);
}
return res;
}
public int centralDiffusion(String A,int left,int right){
//从中心进行扩散，比较
while(left>=0&&right<A.length()){
if(A.charAt(left)==A.charAt(right)){//比较
left--;
right++;
continue;
}
break;//不相等时进行截肢，
}
return right-left+1-2;//计算长度不报left，right所在字符
}
}
3.动态规划
用一个典型的dp二维数组，判断从i到j的字符串是否为回文串，如果是统计长度，动态规划，采用的是从边缘逐渐向内部靠近。时间复杂度为O（n2），两次循环，空间复杂度：O（n2），dp数组。
import java.util.*;

public class Solution {
public int getLongestPalindrome(String A, int n) {
// write code here
if(n==0||n==1)
return n;
int res=0;
boolean dp[][]=new boolean[n][n];//用于判断i到j是否为回文串
for(int len=0;len<=n+1;len++){//子串长度
for(int i=0;i+len<n;i++){//子串的起始位置
int j=i+len;//子串的末尾位置
if(len==0){//子串长度为1一定为回文串
dp[i][j]=true;
}else if(len==1){//子串长度为2
dp[i][j]=(A.charAt(i)==A.charAt(j));
}else{//子串长度大于2
if(A.charAt(i)==A.charAt(j)){//左右字符已相等需比较内部元素
dp[i][j]=dp[i+1][j-1];
}
}
if(dp[i][j]){
res=len+1;
}
}
}
return res;
}
}