Skip to main content

647. Palindromic Substrings

分析

题解

// [l, r] => [l + 1, r - 1]
function countSubstrings(s: string): number {
let ans = 0

const dp = Array.from({ length: s.length }, () => new Array(s.length).fill(false))
for (let l = s.length - 1; l >= 0; l--) {
for (let r = l; r < s.length; r++) {
if (l === r) {
dp[l][r] = true
} else if (l + 1 === r && s[l] === s[r]) {
dp[l][r] = true
} else if (s[l] === s[r]) {
dp[l][r] = dp[l + 1][r - 1]
}
if (dp[l][r]) {
ans++
}
}
}
return ans
};