腾讯&leetcode647：回文子串

[sisterAn]

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

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

示例 1：

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

示例 2：

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

提示：

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

附赠leetcode地址：leetcode

[marlboroKay]

var countSubstrings = function(s) {
  let len = s.length;
  let res = 0;
  for(let i = 0; i < len; i++){
    let str = '';
    let revStr = '';
    for(let j = i; j < len; j++){
      str += s[j];
      revStr = s[j] + revStr;
      if(str === revStr) res++;
    }
  }
  return res;
};

//中心扩展法
var countSubstrings = function(s) {
  let len = s.length;
  let res = 0;
  for(let i = 0; i < 2*len - 1; i++){
    let l = i/2, r = i/2 + i%2;
    while(l >= 0 && r < len && s.charAt(l) == s.charAt(r)){
      l--;
      r++;
      res++;
    }
  }
  return res;
}

[sisterAn]

解法一：暴力法

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(n³)
• 空间复杂度：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(n²)
• 空间复杂度：O(n)

leetcode

[doctorFei]

//中心扩展法
/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function(s) {
    let nums = s.length;
    if(s.length<2){
        return nums
    }
    function lookByCenter(left,right){
        while (left>=0&&right<s.length&&s[left]===s[right]){
            nums++
            left--
            right++
        }
    }

    for (let i = 0;i<s.length;i++){
        lookByCenter(i-1,i+1)
        lookByCenter(i,i+1)
    }

    return nums
};

[TonyZhang1993]

改写自 最长回文子串；

var countSubstrings = function(s) {
  let res = 0

  for (let i=0; i<s.length; i++) {
    // 以 s[i] 为中心的最长回文子串 - 奇数情况
    let s1 = palindrome(s, i, i)
    // 以 s[i] 和 s[i+1] 为中心的最长回文子串 - 偶数情况
    let s2 = palindrome(s, i, i+1)

    res += s1
    res += s2

  }

  return res

  // 在 s 中寻找以 s[l] 和 s[r] 为中心的最长回文串
  function palindrome(s, l, r) {
    let res = 0
    //  边界情况
    while (l>=0 && r<s.length && s[l] === s[r]) {
      //  向两边展开
      l--
      r++
      res++
    }

    // return s.slice(l+1, r)
    return res
  }
}

//  时间复杂度：O(n2)
//  空间复杂度：O(1)