经典算法题 - 回文子串 - 先先的个人博客

前言

1	`经济萧条导致了移动端开发岗的锐减，当前环境下研发人员的竞争尤其激烈。算法，成为了面试大厂的必备条件。`

知识点

双指针、中心拓展法、动态规划

描述

给你一个字符串 s ，请你统计并返回这个字符串中回文子串的数目。
回文字符串是正着读和倒过来读一样的字符串。
子字符串是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例1

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

示例2

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

思路

这题我第一时间想到暴力破解法求解，虽然能 AC，但效果不佳。
标准的解法是使用中心拓展法，创新思维。
当然，动态规划也是一个好解法

代码1，暴力法

暴力法的基本思路是找出 s 的所有子串，
对所有子串一一判断是否为回文

/**
 * 暴力法，直接找出字符串 s 的所有子串，判断是否为回文
 * 如果是回文则 res + 1
 * 最后返回总数 res
 */
function solution(s) {
    // 单字符串直接返回
    if (s.length === 1) {
        return 1;
    }
    // 返回值
    let res = 0;
    // 单次截取子串长度
    let len = 1;
    // 准备用循环来截取子串
    while (len <= s.length) {
        // 注意判断条件
        for (let i = 0; i <= s.length - len; i++) {
            // 一定要注意，substring 的两个参数是 start 和 end，和Java不一样
            let temp = s.substring(i, i + len);
            // 如果是回文，则 + 1
            if (isHuiWen(temp)) {
                res++;
            }
        }
        len++;
    }
    return res;
}

/**
 * 判断字符串 s 是否为回文
 */
function isHuiWen(s) {
    if (s.length === 1) {
        return true;
    }
    let l = 0;
    let r = s.length - 1;
    while (l < r) {
        if (s.charAt(l++) !== s.charAt(r--)) {
            return false;
        }
    }
    return true;
}

代码2，中心拓展法

中心拓展法的基本思路是从 s 的任意位置进行单或双子字符进行拓展判断。
如果子字符串是回文，则向左右拓展
一直拓展到不能拓展为止
其难点在于循环的长度，
另外要格外注意 JavaScript 和 Java 之间的差异点

/**
 * 中心拓展法，其基本思想为:
 * 由中心点开始判断是否为回文，是回文则向外拓展到不是回文为止
 * 中心点的位置是本题的关键，举个例子，abcd 四个字符的拓展点有:
 * 00 -> (a), 01 -> (ab),
 * 11 -> (b), 12 -> (bc),
 * 22 -> (c), 23 -> (cd),
 * 33 -> (d)
 * 也就是说一共有 2n - 1个开始点，坐标分别为 l = i / 2, r = (i + 1) / 2
 */
function countSubstrings(s) {
    let res = 0;
    let len = s.length;
    // 注意遍历数据的长度，上面的注释解释了为什么是 2n - 1
    for (let i = 0; i < len * 2 - 1; i++) {
        // 注意 JavaScript 和 Java 不一样，整数相除为小数，坑啊
        let l = Math.floor(i / 2);
        let r = Math.floor((i + 1) / 2);
        // 注意 l-- 和 r++ 才是左右拓展，别搞反了，搞反了就是死循环
        while (l >= 0 && r < len && s.charAt(l--) === s.charAt(r++)) {
            res++;
        }
    }
    return res;
}