题目

给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。

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

示例 1：输入：s = "abc" 输出：3

解释：三个回文子串: "a", "b", "c"

示例 2：输入：s = "aaa" 输出：6

解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：1 <= s.length <= 1000

s 由小写英文字母组成

注意：本题与主站 647 题相同：

解题思路分析

1、中心扩展；时间复杂度O(n^2)，空间复杂度O(1)

func countSubstrings(s string) int {
   n := len(s)
   res := 0
   for i := 0; i < 2*n-1; i++ {
      left, right := i/2, i/2+i%2
      for ; 0 <= left && right < n && s[left] == s[right]; left, right = left-1, right+1 {
         res++
      }
   }
   return res
}

2、Manacher算法；时间复杂度O(n^2)，空间复杂度O(1)

func countSubstrings(s string) int {
   if len(s) <= 1 {
      return len(s)
   }
   str := add(s)
   length := len(str)
   res := 0
   for i := 0; i < length; i++ {
      curLength := search(str, i)
      res = res + curLength/2 + curLength%2
   }
   return res
}

func add(s string) string {
   var res []rune
   for _, v := range s {
      res = append(res, '#')
      res = append(res, v)
   }
   res = append(res, '#')
   return string(res)
}

func search(s string, center int) int {
   i := center - 1
   j := center + 1
   step := 0
   for ; i >= 0 && j < len(s) && s[i] == s[j]; i, j = i-1, j+1 {
      step++
   }
   return step
}

3、Manacher算法；时间复杂度O(n)，空间复杂度O(n)

func countSubstrings(s string) int {
   var res []rune
   res = append(res, '#39;)
   for _, v := range s {
      res = append(res, '#')
      res = append(res, v)
   }
   res = append(res, '#')
   res = append(res, '!')
   str := string(res)
   n := len(str) - 1
   arr := make([]int, n)
   leftMax, rightMax, result := 0, 0, 0
   for i := 1; i < n; i++ {
      if i <= rightMax {
         arr[i] = min(rightMax-i+1, arr[2*leftMax-i])
      } else {
         arr[i] = 1
      }
      for str[i+arr[i]] == str[i-arr[i]] {
         arr[i]++
      }
      if i+arr[i]-1 > rightMax {
         leftMax = i
         rightMax = i + arr[i] - 1
      }
      result = result + arr[i]/2
   }
   return result
}

func min(a, b int) int {
   if a > b {
      return b
   }
   return a
}

4、动态规划；时间复杂度O(n^2)，空间复杂度O(n^2)

func countSubstrings(s string) int {
   if len(s) <= 1 {
      return len(s)
   }
   dp := make([][]bool, len(s))
   res := 0
   for r := 0; r < len(s); r++ {
      dp[r] = make([]bool, len(s))
      dp[r][r] = true
      res++
      for l := 0; l < r; l++ {
         if s[l] == s[r] && (r-l <= 2 || dp[l+1][r-1] == true) {
            dp[l][r] = true
         } else {
            dp[l][r] = false
         }
         if dp[l][r] == true {
            res++
         }
      }
   }
   return res
}

5、暴力法；时间复杂度O(n^3)，空间复杂度O(1)

func countSubstrings(s string) int {
   if len(s) <= 1 {
      return len(s)
   }
   res := len(s)
   for i := 0; i < len(s)-1; i++ {
      for j := i + 1; j < len(s); j++ {
         if s[i] == s[j] && judge(s, i, j) == true {
            res++
         }
      }
   }
   return res
}

func judge(s string, i, j int) bool {
   for i <= j {
      if s[i] != s[j] {
         return false
      }
      i++
      j--
   }
   return true
}

总结

Medium题目，题目同leetcode 647.回文子串，类似的题目还有 leetcode 5.最长回文子串