647.回文子串

题目描述

题解

动态规划

这道题要区别与第5题, 第5题是求最长的回文子串, 这道题是求回文子串的数量

所以第5题的状态描述为dp[i][j]表示字符串i...j范围内最长的回文子串长度

这道题dp[i][j]为布尔值, 表示子串i...j是否为回文子串

动态转移方程为

dp[j][i] = s.charAt(i) == s.charAt(j) && (i - j < 2 || dp[j + 1][i - 1]);

每当新判断出一个回文子串, 就将结果值++

public class lc647 {
    public int countSubstrings(String s) {
        int count = s.length();
        boolean[][] dp = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
        }


        for (int j = s.length() - 2; j >= 0; j--) {
            for (int i = j + 1; i < s.length(); i++) {
                dp[j][i] = s.charAt(i) == s.charAt(j) && (i - j < 2 || dp[j + 1][i - 1]);
                if (dp[j][i]) {
                    count++;
                }
            }
        }

        return count;
    }


    public static void main(String[] args) {
        lc647 lc647 = new lc647();
        String test = "fdsklf";
        System.out.println(lc647.countSubstrings(test));
    }
}

中心扩散

找到一个中心点, 然后从该点往两边扩散, 根据端的字符是否相同来判断是否为回文子串

public int countSubstrings(String s) {
    // 中心扩展法
    int ans = 0;
    for (int center = 0; center < 2 * s.length() - 1; center++) {
        // left和right指针和中心点的关系是？
        // 首先是left，有一个很明显的2倍关系的存在，其次是right，可能和left指向同一个（偶数时），也可能往后移动一个（奇数）
        // 大致的关系出来了，可以选择带两个特殊例子进去看看是否满足。
        int left = center / 2;
        int right = left + center % 2;

        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            ans++;
            left--;
            right++;
        }
    }
    return ans;
}