Medium | LeetCode 647. 回文子串 | 动态规划 | 中心拓展法

647. 回文子串

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

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

示例 1：

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

示例 2：

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

提示：

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

解题思路

此题与 Medium | LeetCode 5. 最长回文子串 | 动态规划 | 中心拓展法 类似

方法一： 动态规划

public int countSubstrings(String s) {
    int len = s.length();
    boolean[][] dp = new boolean[len][len];
    dp[0][0] = true;
    for(int i = 1; i < len; i++) {
        if(s.charAt(i) == s.charAt(i-1)) {
            // 初始化只有两个数的情况
            dp[i-1][i] = true;
        }
        // 初始化对角线
        dp[i][i] = true;
    }
    // 计算3, 4, 5...N 个数时, 动态规划的数字的个数
    for(int step = 2; step < len; step++) {
        for(int i = 0; i < len - step; i++) {
            if(dp[i + 1][i + step - 1] && s.charAt(i) == s.charAt(i+step)) {
                dp[i][i+step] = true;
            }
        }
    }
    // 计算数组的个数
    int count = 0;
    for(int i = 0; i < len; i++) {
        for(int j = i; j < len; j++) {
            if (dp[i][j]) {
                count++;
            }
        }
    }
    return count;
}

方法二： 中心拓展法

public int countSubstrings(String s) {
    int n = s.length(), ans = 0;
    for (int i = 0; i < 2 * n - 1; ++i) {
        int l = i / 2, r = i / 2 + i % 2;
        while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
            --l;
            ++r;
            ++ans;
        }
    }
    return ans;
}