关于javascript:码不停题算法篇回文子串

40次阅读

共计 801 个字符,预计需要花费 3 分钟才能阅读完成。

题目

给定一个字符串,你的工作是计算这个字符串中有多少个回文子串。

具备不同开始地位或完结地位的子串,即便是由雷同的字符组成,也会被视作不同的子串。

示例 1:

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

示例 2:

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

提醒:

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

题解思路

只须要留神一点: 具备不同开始地位或完结地位的子串,即便是由雷同的字符组成,也会被视作不同的子串

回文子串说的通俗易懂一点,其实就是,正着读和反着读是一样的,比方“aba”,就一共是 4 个回文子串。

解题思路就是遍历两边字符串,第一遍的时候,既然每个字母都能够是独自的子串,那么,第一次遍历的时候,有几个字母就加几。第二次遍历,须要将以后字母跟前面的字母进行比拟,如果遇到雷同的字母,还须要进一步判断,正着读跟反着读是不是一样。是的话,子串数量加一。

代码实现

/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function(s) {if (!s) return 0;
    const sArr = s.split(''); // 字符串转数组
    let count = 0; // 子串的总数量
    for (let i = 0; i < s.length; i ++) {
        count ++; // 第一次遍历每个字母都是独自的子串,都加一
        for (let j = i + 1; j < s.length; j ++) {if (sArr[i] === sArr[j]) {// 第二次遍历首要要求就是前后 两个字母雷同
                if (s.substring(i, j + 1) === s.substring(i, j + 1).split('').reverse().join('')) { // 字母雷同是首要,还须要正反都雷同
                    count ++; // 满足正反雷同持续加一
                }
            }
        }
    }
    return count;
};

正文完
 0