给你一个字符串 s
,请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。
示例 1:
输入:s = "abc" 输出:3 解释:三个回文子串: "a", "b", "c"
示例 2:
输入:s = "aaa" 输出:6 解释:6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示:
1 <= s.length <= 1000
s
由小写英文字母组成
方法一:从中心向两侧扩展回文串
时间复杂度 s
的长度。
方法二:Manacher 算法
在 Manacher 算法的计算过程中,用
时间复杂度 s
的长度。
class Solution:
def countSubstrings(self, s: str) -> int:
ans, n = 0, len(s)
for k in range(n * 2 - 1):
i, j = k // 2, (k + 1) // 2
while ~i and j < n and s[i] == s[j]:
ans += 1
i, j = i - 1, j + 1
return ans
class Solution:
def countSubstrings(self, s: str) -> int:
t = '^#' + '#'.join(s) + '#$'
n = len(t)
p = [0 for _ in range(n)]
pos, maxRight = 0, 0
ans = 0
for i in range(1, n - 1):
p[i] = min(maxRight - i, p[2 * pos - i]) if maxRight > i else 1
while t[i - p[i]] == t[i + p[i]]:
p[i] += 1
if i + p[i] > maxRight:
maxRight = i + p[i]
pos = i
ans += p[i] // 2
return ans
class Solution {
public int countSubstrings(String s) {
int ans = 0;
int n = s.length();
for (int k = 0; k < n * 2 - 1; ++k) {
int i = k / 2, j = (k + 1) / 2;
while (i >= 0 && j < n && s.charAt(i) == s.charAt(j)) {
++ans;
--i;
++j;
}
}
return ans;
}
}
class Solution {
public int countSubstrings(String s) {
StringBuilder sb = new StringBuilder("^#");
for (char ch : s.toCharArray()) {
sb.append(ch).append('#');
}
String t = sb.append('$').toString();
int n = t.length();
int[] p = new int[n];
int pos = 0, maxRight = 0;
int ans = 0;
for (int i = 1; i < n - 1; i++) {
p[i] = maxRight > i ? Math.min(maxRight - i, p[2 * pos - i]) : 1;
while (t.charAt(i - p[i]) == t.charAt(i + p[i])) {
p[i]++;
}
if (i + p[i] > maxRight) {
maxRight = i + p[i];
pos = i;
}
ans += p[i] / 2;
}
return ans;
}
}
class Solution {
public:
int countSubstrings(string s) {
int ans = 0;
int n = s.size();
for (int k = 0; k < n * 2 - 1; ++k) {
int i = k / 2, j = (k + 1) / 2;
while (~i && j < n && s[i] == s[j]) {
++ans;
--i;
++j;
}
}
return ans;
}
};
func countSubstrings(s string) int {
ans, n := 0, len(s)
for k := 0; k < n*2-1; k++ {
i, j := k/2, (k+1)/2
for i >= 0 && j < n && s[i] == s[j] {
ans++
i, j = i-1, j+1
}
}
return ans
}
/**
* @param {string} s
* @return {number}
*/
var countSubstrings = function (s) {
let ans = 0;
const n = s.length;
for (let k = 0; k < n * 2 - 1; ++k) {
let i = k >> 1;
let j = (k + 1) >> 1;
while (~i && j < n && s[i] == s[j]) {
++ans;
--i;
++j;
}
}
return ans;
};