BFE.devAI解答 - JavaScript 代码题
111. 回文子字符串数量
解法一：暴力枚举
我们可以枚举所有的子串，然后判断其是否为回文串。
具体地，我们枚举子串的左边界和右边界，确定了这些以后，就可以判断该子串是否为回文串了。
时间复杂度分析：一共有 $n^2$ 个子串，对于每个子串，需要 $O(n)$ 的时间来判断它是否为回文串，因此总时间复杂度为 $O(n^3)$。空间复杂度为 $O(1)$。
代码如下：
/**
* @param {string} s
* @return {number}
*/
function countSubstrings(s) {
let ans = 0;
const n = s.length;
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
if (isPalindrome(s, i, j)) {
ans++;
}
}
}
return ans;
}
function isPalindrome(s, i, j) {
while (i < j) {
if (s[i] !== s[j]) {
return false;
}
i++;
j--;
}
return true;
}解法二：中心扩展法
注意到回文串一定是中心对称的，因此我们可以枚举每个回文串的中心位置，然后向两边扩展，判断左右是否相同。
注意到中心位置一共有 $2n-1$ 个，因此总时间复杂度为 $O(n^2)$，空间复杂度为 $O(1)$。
代码如下：
/**
* @param {string} s
* @return {number}
*/
function countSubstrings(s) {
let ans = 0;
const n = s.length;
for (let i = 0; i < 2 * n - 1; i++) {
let left = Math.floor(i / 2);
let right = left + i % 2;
while (left >= 0 && right < n && s[left] === s[right]) {
ans++;
left--;
right++;
}
}
return ans;
}解法三：动态规划
我们使用动态规划的方法，定义 $dp(i, j)$ 表示区间 $[i, j]$ 是否为回文子串，转移方程为：
$$ dp(i, j) = \begin{cases} true, & \text{if } i \ge j \ s_i = s_j, & \text{if } i < j \ false, & \text{if } i < j \text{ and } s_i \neq s_j \end{cases} $$
即如果区间 $[i, j]$ 为空串，那么它一定是回文子串；如果区间 $[i, j]$ 不为空且 $s_i = s_j$，那么它是回文子串当且仅当区间 $[i+1, j-1]$ 是回文子串；否则它不是回文子串。
注意到 $i \le j$，因此 $dp(i, j)$ 中 $i$ 不大于 $j$，我们只需要枚举 $i$ 和 $j$ 之间的距离（即 $j-i$），依次计算 $dp(i, j)$ 即可。
时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$。
代码如下：
/**
* @param {string} s
* @return {number}
*/
function countSubstrings(s) {
let ans = 0;
const n = s.length;
const dp = Array.from({ length: n }, () => new Array(n).fill(false));
for (let len = 1; len <= n; len++) {
for (let i = 0; i < n; i++) {
let j = i + len - 1;
if (j >= n) {
break;
}
if (len === 1) {
dp[i][j] = true;
} else if (len === 2) {
dp[i][j] = (s[i] === s[j]);
} else {
dp[i][j] = (s[i] === s[j] && dp[i+1][j-1]);
}
if (dp[i][j]) {
ans++;
}
}
}
return ans;
}解法四：Manacher 算法
这是一个比较巧妙的算法，可以在 $O(n)$ 的时间内求出所有回文子串。
Manacher 算法与解法二类似，也是中心扩展法，但是它通过预处理来避免了重复的计算。
具体地，我们可以先在字符串 $s$ 的每个相邻两个字符之间（包括开头和结尾）插入一个特殊字符（比如 #），这样得到的字符串长度一定是奇数。
然后从左向右遍历字符串，用 $P_i$ 表示以字符 $s_i$ 为中心向两边扩展的最长回文串长度，我们用 $R$ 表示当前能够扩展的最右边界，$C$ 表示当前能够扩展的最右边界对应的回文串的中心位置。每次遍历到一个新的字符 $s_i$ 时，分为两种情况：
- 如果 $i \le R$，则有可能通过之前的信息，更新 $P_i$ 的值；
- 如果 $i > R$，则需要从 $s_i$ 为中心向两边扩展，同时更新 $R$ 和 $C$。
注意到如果 $P_i$ 表示以字符 $s_i$ 为中心的回文串长度，那么实际上 $P_i-1$ 就是以字符 $s_i$ 左边那个特殊字符为中心的回文串长度，$P_i+1$ 就是以字符 $s_i$ 右边那个特殊字符为中心的回文串长度，因此我们有如下转移公式：
$$ \begin{cases} P_i = 1 & \text{if } i > R \ P_i = \min(P_{2C-i}, R-i+1) & \text{otherwise} \end{cases} $$
其中第一种情况表示当前位置在 $R$ 的右侧，无法继续利用已经得到的信息，只能从 $s_i$ 为中心扩展，因此长度为 $1$；第二种情况表示当前位置在 $[L, R]$ 内部，可以根据它对称的位置更新 $P_i$ 的值。
时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。
代码如下：
/**
* @param {string} s
* @return {number}
*/
function countSubstrings(s) {
const t = `#${s.split('').join('#')}#`;
const n = t.length;
const p = new Array(n).fill(0);
let R = 0, C = 0, ans = 0;
for (let i = 0; i < n; i++) {
if (i <= R) {
p[i] = Math.min(p[2*C-i], R-i+1);
} else {
p[i] = 1;
}
while (i - p[i] >= 0 && i + p[i] < n && t[i-p[i]] === t[i+p[i]]) {
p[i]++;
}
if (i + p[i] - 1 > R) {
R = i + p[i] - 1;
C = i;
}
ans += Math.floor((p[i] - 1) / 2);
}
return ans;
}参考文献：