647. Palindromic Substrings

[Tcdian]

647. Palindromic Substrings

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

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

Example 1

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Note

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

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function(s) {
    const dp = Array.from(new Array(s.length), () => new Array(s.length));
    let result = 0;
    for (let i = 0; i < s.length; i++) {
        for (let j = i; j >= 0; j--) {
            if (i === j) {
                dp[j][j] = true;
            } else if (i === j + 1) {
                dp[j][i] = s[i] === s[j];
            } else {
                dp[j][i] = s[i] === s[j] ? dp[j + 1][i - 1] : false;
            }
            result += dp[j][i] ? 1 : 0;
        }
    }
    return result;
};

• TypeScript Solution

function countSubstrings(s: string): number {
    const dp: boolean[][] = Array.from(new Array(s.length), () => new Array(s.length));
    let result = 0;
    for (let i = 0; i < s.length; i++) {
        for (let j = i; j >= 0; j--) {
            if (i === j) {
                dp[j][j] = true;
            } else if (i === j + 1) {
                dp[j][i] = s[i] === s[j];
            } else {
                dp[j][i] = s[i] === s[j] ? dp[j + 1][i - 1] : false;
            }
            result += dp[j][i] ? 1 : 0;
        }
    }
    return result;
};