package dynamic;

/**
 * 题目:求回文子串的个数
 *
 * y: abc 3个
 * aba 4个
 */
public class solution_1 {
 /**
 * 第一种方法就是暴力破解法使用for循环,时间复杂度为O(n^3),空间复杂度为O(1)
 *
 * 第二种方法:使用一个二维数组来存储子串是否是回文字符串,把结果存下来就是动态规划
 * 的解法,可以节约O(n)的复杂度,是一种空间换时间的概念
 * 从外层到内层依次进行判断字符串,这里节约的时间就是把每次判断是否是回文的状态存储到
 * 数组里面了,这就节约了时间复杂度
 */
 //Time:O(n^2) Space:O(n)
 public static int solution_1(String s){
 if(s==null||s.length()==0)return 0;
 int n=s.length(),count=0;
 boolean[][] d=new boolean[n][n];
 for (int i=n-1;i>=0;--i){//数组下标是从0开始,所以n-1表示的是最后一个字符
 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;
 //这里就是精华部分了
 /**
 * 因为我们的循环已经处理好相等的时候,相邻的时候的状态了,这里我们就只需要判断i+1和j-1就行了
 * 都是依次递进的关系
 * 比如这里比较abcmda
 * 在比较b和d两个字符的时候a和a已经比较过了
 * 在比较c和m的时候ab和da的状态也已经比较好了
 *
 */
 else d[i][j]= b &&d[i+1][j-1];
 }
 if(d[i][j])++count;
 }
 }
 return count;
 }

 /**
 * 第三种方法:
 * 由某个字符向两边扩展进行对比
 * 这种方式比较容易理解
 * 比如比较: abcdef
 * 先比较 a
 * 然后 b ba
 * 然后 c cb cba
 * 依次遍历完就行
 */
 //Time:O(n^2) Space:O(1)
 public int solution_2(String s){
 if(s==null||s.length()==0)return 0;
 int count=0;
 for (int i = 0; i < s.length(); i++) {
 count+=puStr(s,i,i);
 count+=puStr(s,i,i+1);//以两个数为中心向两边扩展
 }
 return count;
 }
 //求一个字符串回文串的个数
 int puStr(String s,int left , int right){
 int count=0;
 while (left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){
 ++count;
 --left;
 ++right;
 }
 return count;
 }


 public static void main(String[] args) {
 System.out.println(solution_1("abc"));
 }
}