回忆复习 递归中，分割回文子串那道题。 131.
1652769629(1).png

思路

1.dp

布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。
当s[i]与s[j]不相等，那没啥好说的了，dp[i][j]一定是false。
当s[i]与s[j]相等时，这就复杂一些了，有如下三种情况

  • 情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
  • 情况二：下标i 与 j相差为1，例如aa，也是回文子串
  • 情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。
  • 时间复杂度：$O(n^2)$

  • 空间复杂度：$O(n^2)$

    1. var countSubstrings = function(s) {
    2.   // dp解法
    3.   // dp[i][j],s[i]-s[j]是不是回文子串,两端闭合
    5.   let dp =Array.from(Array(s.length),()=>Array(s.length).fill(false))
    6.   let result =0
    8.   // 先遍历列，再遍历行，保证递推的来源dp[i+1][j-1]是先被计算
    9.   for(let j=0;j<s.length;j++){
    10.       for(let i=0;i<=j;i++){
    11.           if(s[i]===s[j]){
    12.               if(j-i<=1){
    13.                   // s[i]-s[j]长度为1 or 2,此时一定是回文
    14.                   dp[i][j]=true
    15.               }else{
    16.                   // 否则判断中间的i+1 到 j-1这中间子串是不是回文，递推
    17.                   dp[i][j] =dp[i+1][j-1]
    18.                }
    19.                result += dp[i][j]?1 :0
    20.           }
    21.       }
    22.   }
    23.   return result
    24. };

    2. 中心扩散法

    1652840863(1).png

    分别讨论

    var countSubstrings = function(s) {
  // 中心扩散法
  let result =0
  const findPalindrome =function(s,left,right){
      let res =0
      while(left>=0&&right<s.length&&s[left]===s[right]){
          res++
          left--
          right++
      }
      return res
  }

  for(let i=0;i<s.length;i++){
      // 当中心为1个时
      result+=findPalindrome(s,i,i)
      // 当中心为2个时
      result+= findPalindrome(s,i,i+1)
  }

  return result
};

  • 时间复杂度：$O(n^2)$

  • 空间复杂度：$O(1)$

    统一讨论

    这种可以将left和right统一起来，循环次数时 2^n -1（因为有n个单独中心和 n-1个双中心）
    我觉得不是很好理解，

    3.Manacher（马拉车）算法

    4. 暴力（n^3超时）