一、问题描述
给定一个字符串 s，你的任务是计算这个字符串中有多少个回文子串。 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。 示例 1:
输入: "abc"
输出: 3
解释: 三个回文子串: "a", "b", "c".示例 2:
输入: "aaa"
输出: 6
说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".注意:
- 输入的字符串长度不会超过1000。
二、方案一：暴力法
1、思路
暴力法是最直接的方法。对于字符串 s 中的每个子串，我们检查它是否是回文。为了检查一个字符串是否是回文，我们可以使用双指针技术，一个从开始位置，另一个从结束位置向中间移动，并检查字符是否相等。
2、代码实现
go
func countSubstrings(s string) int {
count := 0
for i := 0; i < len(s); i++ {
for j := i; j < len(s); j++ {
if isPalindrome(s[i:j+1]) {
count++
}
}
}
return count
}
func isPalindrome(sub string) bool {
for i, j := 0, len(sub)-1; i < j; i, j = i+1, j-1 {
if sub[i] != sub[j] {
return false
}
}
return true
}3、复杂度分析
- 时间复杂度：O(n^3)，其中 n 是字符串的长度。我们需要检查每个子串是否是回文，这需要 O(n) 的时间，因此总的时间复杂度是 O(n^3)。
- 空间复杂度：O(1)，我们只需要常数级别的额外空间。
三、方案二：动态规划
1、思路
动态规划可以用来优化暴力法。我们定义一个二维数组 dp[i][j]，表示字符串从索引 i 到 j 的子串是否是回文。如果 s[i] == s[j] 并且 (j - i <= 2 || dp[i+1][j-1])，那么 dp[i][j] 是 true。
2、代码实现
go
func countSubstrings(s string) int {
n := len(s)
dp := make([][]bool, n)
for i := range dp {
dp[i] = make([]bool, n)
}
count := 0
for i := n - 1; i >= 0; i-- {
for j := i; j < n; j++ {
if s[i] == s[j] && (j - i <= 2 || dp[i+1][j-1]) {
dp[i][j] = true
count++
}
}
}
return count
}3、复杂度分析
- 时间复杂度：O(n^2)，其中 n 是字符串的长度。我们需要检查每个子串是否是回文，这需要 O(1) 的时间，因此总的时间复杂度是 O(n^2)。
- 空间复杂度：O(n^2)，我们需要一个二维数组来存储动态规划的状态。
四、方案三：中心扩展法
1、思路
回文子串的中心可以是一个字符，也可以是两个字符之间。我们可以从每个可能的中心开始，向两边扩展，检查是否是回文。这样我们只需要 O(n) 的时间复杂度。
2、代码实现
go
func countSubstrings(s string) int {
count := 0
for center := 0; center < 2*len(s)-1; center++ {
left := center / 2
right := left + center%2
for left >= 0 && right < len(s) && s[left] == s[right] {
count++
left--
right++
}
}
return count
}3、复杂度分析
- 时间复杂度：O(n^2)，其中 n 是字符串的长度。虽然看起来是两层循环，但实际上每个字符只被访问了一次。
- 空间复杂度：O(1)，我们只需要常数级别的额外空间。
五、总结
| 方案 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 暴力法 | O |