给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。
输入:"abc"
输出:3
解释:三个回文子串: "a", "b", "c"
输入:"aaa"
输出:6
解释:6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
抛砖引玉
思路
之前做过验证回文串的题目:20200619:验证回文串 (难度:简单)[2]既然可以验证一个字符串是否为回文字符串了,那么就只剩枚举字符串的子区间了
/**
* @param {string} s
* @return {number}
*/
var countSubstrings = function (s) {
let _result = 0
// 枚举区间
for (let i = 0; i < s.length; i++) {
for (let j = i; j < s.length; j++) {
if (check(i, j + 1)) {
_result++
}
}
}
return _result
// 验证回文串
function check(i, j) {
let str = s
.substring(i, j)
.replace(/[^0-9a-zA-Z]/g, '')
.toLowerCase(),
n = str.length,
left = 0,
right = n - 1
while (left < right) {
if (str[left] != str[right]) {
return false
}
left++
right--
}
return true
}
}
通过区间来枚举可能是回文字符串中心位置的元素
var countSubstrings = function (s) {
let len = s.length,
_result = 0
for (let i = 0; i < 2 * len - 1; ++i) {
let left = parseInt(i / 2, 10),
right = Math.ceil(i / 2)
while (left >= 0 && right < len && s.charAt(left) === s.charAt(right)) {
--left
++right
++_result
}
}
return _result
}
var countSubstrings = function (s) {
let len = s.length,
_result = 0,
dp = Array(len)
for (let i = 0; i < len; i++) {
dp[i] = Array(len).fill(false)
}
for (let j = 0; j < len; j++) {
for (let i = 0; i <= j; i++) {
if (i == j) {
dp[i][j] = true
_result++
} else if (j - i == 1 && s[i] == s[j]) {
dp[i][j] = true
_result++
} else if (j - i > 1 && s[i] == s[j] && dp[i + 1][j - 1]) {
dp[i][j] = true
_result++
}
}
}
return _result
}
降维
var countSubstrings = function (s) {
let len = s.length,
_result = 0,
dp = Array(len)
for (let j = 0; j < len; j++) {
for (let i = 0; i <= j; i++) {
if (s[i] == s[j] && (j - i <= 1 || dp[i + 1])) {
dp[i] = true
_result++
} else {
dp[i] = false
}
}
}
return _result
}
初始化对称半径,当前元素索引 i:
扩展中心位置:中心位置 i,初始化的对称为 f[i],那么已知:s[i+f(i)-1] === s[i-f(i)+1] 扩张该中心位置的对称字符时,下一个要比较的元素:s[i+f(i)] === s[i-f(i)],如果相同修改 f(i)、即记录的半径变大,知道遇到不相同的元素
为了避免枚举的中心位置可能自己独立成中心也可能与其他元素相同,则修改原字符串 s:在原字符串中间隔插入字符#,并且标记开始结束(开始结束标记不同字符)
返回结果
var countSubstrings = function (s) {
let t = ['$', '#'],
radius = 0,
right = 0,
_result = 0
// 在字符中间隔插入#,首尾添加 $,!
for (let i = 0; i < s.length; ++i) {
t.push(s.charAt(i))
t.push('#')
}
let n = t.length,
f = new Array(n)
t = t.join('')
t += '!'
for (let i = 1; i < n; ++i) {
// 初始化i开始半径
let j = 2 * radius - i
f[i] = i <= right ? Math.min(right - i + 1, f[j]) : 1
// 查找i作为中心位置的最大半径
while (t.charAt(i + f[i]) == t.charAt(i - f[i])) {
++f[i]
}
// i作为中心如果大于上一个有边界则拓展右边界
if (i + f[i] - 1 > right) {
radius = i
right = i + f[i] - 1
}
// 前两位为 $#,均忽略
_result += Math.floor(f[i] / 2)
}
return _result
}
参考资料
[1]
题目:: https://leetcode-cn.com/problems/palindromic-substrings/