回文子串

题目描述

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

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

示例

示例1

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

示例2

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

解决思路

方法1 暴力破解

我们用ababa做例子, 对字符串做遍历，i 表示字符串的第n个数

  • i = 0, 字符 a, 判断一下是否是回文，是的话count + 1。 此时我们保留上一次的字符['a']
  • i = 1, 字符 b, 此时我们对上一次字符数组的所有子串都添加b, 注意这里也要加上自身b, 也就是 ['b', 'ab'] 去判断一下是否是回文，此时再将上面数组保留下来。
  • i = 2, 字符 c, 我们继续做上面的操作, 先记录自身c, 再对上面保留下来的字符做c字符添加，也就是 ['c', 'bc', 'abc'], 对数组做回文判断，如此类推

我们总结一下，看下每次操作的数组

  1. ['a']
  2. ['b', 'ab']
  3. ['c', 'bc', 'abc']
  4. ['b', 'cb', 'bcb', 'abcb'],
  5. ['a', 'ba', 'cba', 'bcba', 'abcb']
// 完整代码
/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function(s) {
    let count = 0;
    let length = s.length;

    if(length === 0) {
        return count
    }

    let prev = [s[0]];
    count = 1;

    for(let i = 1; i < length; i++) {
        let current = [s[i]];
        count++;

        for(let j = 0; j < prev.length; j++) {
            let temp = prev[j] + s[i];
            if(ishuiwen(temp)) {
                count++;
            }
            current.push(temp);
        }
        prev = current;
    }
    return count;
};

var ishuiwen = function(s) {
    let start = 0;
    let end = s.length - 1;

    while(start < end) {
        let ss = s[start];
        let es = s[end];

        if(ss !== es) {
            return false
        }

        start++;
        end--
    } 
    return true
}

方法二 动态规划

题解

上面 s[i][j] 指的是 s[i:j] 的子串, 比如 i = 1, j = 3, 以ababa 例子, s[i:j] => s[1:3] 就是字符串中的bab