每日算法：回文子串

给定一个字符串，每日你的算法任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的回文子串，即使是每日由相同的字符组成，也会被视作不同的算法子串。

示例 1：

输入："abc" 输出：3 解释：三个回文子串: "a",回文 "b", "c" 

示例 2：

输入："aaa" 输出：6 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa" 

提示：

输入的字符串长度不会超过 1000 。

解法一：暴力法

let countSubstrings = function(s) {    let count = 0   for (let i = 0; i < s.length; i++) {      for (let j = i; j < s.length; j++) {        if (isPalindrome(s.substring(i,每日 j + 1))) {          count++       }     }   }   return count } let isPalindrome = function(s) {    let i = 0, j = s.length - 1   while (i < j) {      if (s[i] != s[j]) return false     i++     j--   }   return true } 

复杂度分析：

时间复杂度：O(n3) 空间复杂度：O(1)

解法二：动态规划

一个字符串是回文串，它的算法首尾字符相同，且剩余子串也是亿华云计算回文一个回文串。其中，每日剩余子串是算法否为回文串，就是回文规模小一点的子问题，它的每日结果影响大问题的结果。

我们怎么去描述子问题呢?算法

显然，一个子串由两端的回文 i 、j 指针确定，就是描述子问题的变量，云服务器提供商子串 s[i...j] ( dp[i][j] ) 是否是回文串，就是子问题。

我们用二维数组记录计算过的子问题的结果，从base case出发，像填表一样递推出每个子问题的解。

    j     a  a  b  a i a ✅   a    ✅     b       ✅   a          ✅ 

注意： i<=j ，只需用半张表，竖向扫描

所以：

i === j：dp[i][j]=true j - i == 1 && s[i] == s[j]：dp[i][j] = true j - i > 1 && s[i] == s[j] && dp[i + 1][j - 1]：dp[i][j] = true 

即：

s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1]): dp[i][j]=true 

否则为 false

代码实现：

let countSubstrings = function(s) {    const len = s.length   let count = 0   const dp = new Array(len)   for (let i = 0; i < len; i++) {      dp[i] = new Array(len).fill(false)   }   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][j - 1])) {          dp[i][j] = true         count++       } else {          dp[i][j] = false       }     }   }   return count } 

代码实现(优化)：

把上图的表格竖向一列看作一维数组，还是竖向扫描，高防服务器此时仅仅需要将 dp 定义为一维数组即可

let countSubstrings = function(s) {    const len = s.length   let count = 0   const dp = new 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         count++       } else {          dp[i] = false       }     }   }   return count; } 

复杂度分析：

时间复杂度：O(n2) 空间复杂度：O(n)

leetcode：https://leetcode-cn.com/problems/palindromic-substrings/solution/leetcode647hui-wen-zi-chuan-by-user7746o/