Appearance
647. 回文子串
原题链接：LeetCode 647. 回文子串
题目描述
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
示例 1：
- 输入： s = "abc"
- 输出： 3
- 解释： 三个回文子串: "a", "b", "c"
示例 2：
- 输入： s = "aaa"
- 输出： 6
- 解释： 6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：
1 <= s.length <= 1000s由小写英文字母组成
难度： Medium
题解代码
javascript
/**
* @param {string} s
* @return {number}
*/
var countSubstrings = function(s) {
const len = s.length
const dp = Array(len).fill(0).map(() => Array(len).fill(false))
let count = len
for (let i = 0; i < len; i++) {
dp[i][i] = true
}
for (let j = 1; j < len; j++) {
for (let i = 0; i < j; i++) {
if (s[i] !== s[j]) {
dp[i][j] = false
} else if (j - i < 3) { // 中间最多只有一个元素
dp[i][j] = true
} else {
dp[i][j] = dp[i + 1][j - 1]
}
if (dp[i][j]) {
count += 1
}
}
}
return count
};