图片说明

  • 题解
    class Solution {
  public int countSubstrings(String s) {
      int res = 0;
      int n = s.length();
      boolean flag [][] = new boolean[n][n];
      for(int i = 0 ; i < n ; i++){
          flag[i][i] = true;
          res ++;
      }
      for(int i = 0 ; i < n -1 ; i++){
          if(s.charAt(i)==s.charAt(i+1)){
              res++;
              flag[i][i+1] = true;
          }
      }
      for(int len = 3 ; len <= n;len++){
          for(int i = 0; i+len <= n ;i++){
              if(s.charAt(i)==s.charAt(i+len-1)){
                  flag[i][i+len-1] = flag[i+1][i+len-1-1];
                  if( flag[i][i+len-1]==true)
                      res++;
              }
          }
      }
      return res;
  }
}
  • 从中心往两侧延伸【通过】
    在长度为 N 的字符串中，可能的回文串中心位置有 2N-1 个：字母，或两个字母中间。
从每一个回文串中心开始统计回文串数量。回文区间 [a, b] 表示 S[a], S[a+1], ..., S[b] 是回文串，根据回文串定义可知 [a+1, b-1] 也是回文区间。
    图片说明

反思

之前回文子串没有想其他解答，导致思维局限于暴力 现在看了几种解答 可以利用中心扩散来求解 也就是在2*n－1的位置进行遍历
解答二是动态规划 从1个长度到n个长度进行查找 头相等找中间 而中间是利用之前的统计结果来求解 也形成更好的动态规划模型