647. 回文子串

1. 题目描述

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

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

示例 1：

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

示例 2：

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

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

2. 解题思路

这个题目使用暴力方法解决的，遍历每一种可能，具体思路如下：

• 首先，根据题目，我们可以看出，每个元素自身也算是一个回文子串，所以要将字符串的长度加进去
• 定义一个函数用来检测字符串是否是回文串
• 两层遍历字符串，截取字符串的所有的子串，并判断其是否是回文串

这种解题方式的时间复杂度为O(n)，空间复杂度为O(1)

3. 代码实现

/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function(s) {
    let count = s.length
    let len = s.length
    for(let i = 0; i < len; i++){
        for(let j = i + 1; j < len; j++){
            let temp = s.substr(i, j-i+1)
            if(isSub(temp)){
                count++
            }
        }
    }
    return count
};
const isSub = str => {
        let a = 0
        let b = str.length - 1
        while(a <= b){
            if(str[a] !== str[b]){
                return false
            }
            a++
            b--
        }
        return true
    }

4. 提交结果