Description
給定一個字串
s，計算其中有多少個回文子字串。具有不同起始或結束位置的子字串即使內容相同也視為不同的子字串。
Example:
Input: s = “aaa” Output: 6
Intuition#
和最長回文子字串同一套路：從每個中心向外擴展，每擴展成功一次就多一個回文。
- 每個字元本身就是一個回文，所以最少有
n個 - 擴展時每成功一步就 count + 1
- 同樣要考慮奇數和偶數長度的中心
Approaches#
1: Dynamic Programming#
- 概念:
dp[i][j]表示s[i..j]是否為回文，遍歷所有子字串並計數 - 時間複雜度:
O(n^2) - 空間複雜度:
O(n^2)
class Solution {
fun countSubstrings(s: String): Int {
val n = s.length
val dp = Array(n) { BooleanArray(n) }
var count = 0
for (len in 1..n) {
for (i in 0..n - len) {
val j = i + len - 1
dp[i][j] = s[i] == s[j] && (len <= 2 || dp[i + 1][j - 1])
if (dp[i][j]) count++
}
}
return count
}
}⭐2: Expand Around Center#
- 概念: 對每個中心（奇偶兩種）擴展，每次擴展成功就累加計數
- 時間複雜度:
O(n^2) - 空間複雜度:
O(1)
class Solution {
fun countSubstrings(s: String): Int {
var count = 0
fun expand(l: Int, r: Int) {
var left = l; var right = r
while (left >= 0 && right < s.length && s[left] == s[right]) {
count++
left--; right++
}
}
for (i in s.indices) {
expand(i, i) // 奇數長度
expand(i, i + 1) // 偶數長度
}
return count
}
}🔑 Takeaways#
- Pattern: 中心擴展計數 — 與找最長回文子字串相同的框架，只是目標從「最長」變成「計數」
- 關鍵技巧: 擴展過程中每一步都是一個有效回文，不需要額外判斷