SOURCE

// 倒转过来也是一样的字符串就是回文串(palindromic string)，比如'madam'.

// 给定一个字符串，请计算其有多少个回文子串。

// 比如'madam'有如下回文子串

// 'm'
// 'a'
// 'd'
// 'a'
// 'm'
// 'ada'
// 'madam'
// 你的代码的时间空间复杂度是多少？能否优化？

//method1

function countPalindromicSubstr1(str) {
    const len = str.length;
    const res = [];

    const expand = (left, right) => {
        while (left >= 0 && right < len && str[left] === str[right]) {
            res.push(str.slice(left, right + 1));
            left--;
            right++;
        };
    };

    for (let i = 0; i < len; i++) {
        expand(i, i);
        expand(i, i + 1);
    };

    return res;
};

function countPalindromicSubstr2(str) {
    const len = str.length;
    const dp = Array.from({ length: len }, () => Array(len).fill(false));

    const res = [];

    for (let i = len - 1; i >= 0; i--) {
        for (let j = i; j < len; j++) {
            if (str[i] === str[j]) {
                if (j - i <= 1 || dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    res.push(str.slice(i, j + 1));
                }
            }
        }
    };

    return res;
};


console.log(countPalindromicSubstr2('madam'));