class Solution {
public:
int countSubstrings(string s) {
}
};
剑指 Offer II 020. 回文子字符串的个数
给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = "abc" 输出：3 解释：三个回文子串: "a", "b", "c"
示例 2：
输入：s = "aaa" 输出：6 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：
1 <= s.length <= 1000s 由小写英文字母组成
注意：本题与主站 647 题相同：https://leetcode.cn/problems/palindromic-substrings/
原站题解
python3 解法, 执行用时: 92 ms, 内存消耗: 15 MB, 提交时间: 2022-11-19 18:35:33
class Solution:
def countSubstrings(self, s: str) -> int:
n = len(s)
ans = 0
for i in range(0, 2 * n - 1):
l, r = i // 2, i // 2 + i % 2
while l >= 0 and r < n and s[l] == s[r]:
l -= 1
r += 1
ans += 1
return ans
golang 解法, 执行用时: 4 ms, 内存消耗: 4.7 MB, 提交时间: 2022-11-19 18:32:57
func countSubstrings(s string) int {
n := len(s)
t := "$#"
for i := 0; i < n; i++ {
t += string(s[i]) + "#"
}
n = len(t)
t += "!"
f := make([]int, n)
iMax, rMax, ans := 0, 0, 0
for i := 1; i < n; i++ {
// 初始化 f[i]
if i <= rMax {
f[i] = min(rMax - i + 1, f[2 * iMax - i])
} else {
f[i] = 1
}
// 中心拓展
for t[i + f[i]] == t[i - f[i]] {
f[i]++
}
// 动态维护 iMax 和 rMax
if i + f[i] - 1 > rMax {
iMax = i
rMax = i + f[i] - 1
}
// 统计答案, 当前贡献为 (f[i] - 1) / 2 上取整
ans += f[i] / 2
}
return ans
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2022-11-19 18:32:36
func countSubstrings(s string) int {
n := len(s)
ans := 0
for i := 0; i < 2 * n - 1; i++ {
l, r := i / 2, i / 2 + i % 2
for l >= 0 && r < n && s[l] == s[r] {
l--
r++
ans++
}
}
return ans
}