题解 | #回文子串的数量#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param str string字符串
 * @return int整型
 */
function Substrings(str) {
    return resolve2(str);
}

function resolve(str) {
    const N = str.length;
    const dp = Array(N).fill().map(() => Array(N).fill(false));
    let res = 0;
    for(let i = N - 1; i >= 0; i--) {
        for(let j = i; j < N; j++) {
            if(str[i] === str[j] && (j - i <= 1 || dp[i+1][j-1])) {
                res++;
                dp[i][j] = true;
            }
        }
    }

    return res;
}

function resolve2(str) {
    let res = 0;
    const N = str.length;

    const huiwen = (str, i, j) => {
        let count = 0;
        while(i >= 0 && j < N && str[i--] === str[j++]) {
            count++;
        }
        return count;
    }

    for(let i = 0; i < N; i++) {
        res += huiwen(str, i, i);
        res += huiwen(str, i, i + 1);
    }

    return res;
}


module.exports = {
    Substrings: Substrings,
};

双指针中心扩展法和动态规划时间复杂度一致，O(N²)，双指针的空间复杂度是O(1)，动归的空间复杂度是 O(N²)