【Manacher 算法】Leecode-647. 回文子串

【题目】

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

【题解】

题解1：

• 思路

     列出可能的树形图，对于给出的列表逐个遍历调用dfs

• 复杂度

         时间复杂度：O(n2)，空间复杂度：O(n)

• 代码

class Solution:
  def countSubstrings(self, s: str) -> int:
      n = len(s)  
      dp = [[False]*(n+1) for _ in range(n+1)]
      res = 0
      for i in range(n-1,-1,-1):
          for j in range(i,n):
              if s[i]==s[j]:
                  if j-i<=1:
                      dp[i][j] = True 
                      res+=1
                  elif dp[i+1][j-1]:
                      dp[i][j] = True 
                      res+=1
      return res