package dynamic;

/**题目:求最大的回文子串长度
 * @Author Gavin
 * @date 2021年12月28日 21:30
 */
public class solution_3 {
 /**
 * 第一种方式:利用一个二维数组把是回文子串的字符存储起来达到动态规划的目的
 */
 //Time:O(n^2) Space:O(n^2)
 public static String solution_1(String s){
 //首先处理边界值
 if(s==null||s.length()==0)return "";
 int n=s.length(),start=0,maxLen=0;
 boolean[][] d=new boolean[n][n];

 for (int i = n-1; i >=0 ; --i) {
 for (int j = i; j < n; j++) {
 if(i==j)d[i][j]=true;
 else {
 boolean b = s.charAt(i) == s.charAt(j);
 if(i+1==j)d[i][j]= b;
 else d[i][j]= b &&d[i+1][j-1];
 }
 if(d[i][j]&&(j-i+1)>maxLen){
 start=i;
 maxLen=j-i+1;
 }
 }
 }
 return s.substring(start,start+maxLen);
 }
 /**
 * 第二种方法:
 * 使用两个指针left,right进行移动,由中间向两边移动
 */
 //Time:O(n^2) Space:O(1)
 public static String solution_2(String s){
 if(s==null||s.length()==0)return "";
 int start=0,maxLen=0;
 for (int i = 0; i < s.length(); i++) {
 int len1=expand(s,i,i);
 int len2=expand(s,i,i+1);
 int len=Math.max(len1,len2);
 if(len>maxLen){
 //用len=6 i=2的时候容易理解计算start的位置
 start=i-(len-1)/2;//此时i处于中心位置,所以减去一半就是start位置
 maxLen=len;
 }
 }
 return s.substring(start,start+maxLen);
 }
 //求一个字符的回文串长度
 private static int expand(String s,int left,int right){
 while (left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){
 --left;
 ++right;
 }
 //(right-1)-(left+1)+1
 return right-left-1;
 }
}