Description

难度：中等

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

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

示例 2：

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

Solution

暴力搜索

class Solution {
    public int countSubstrings(String s) {
        int count = s.length();
        char[] cs = s.toCharArray();
        // 遍历字符串
        for (int i = 1; i < s.length(); i ++){
            for (int j = 0; j < i; j ++){
                if (cs[j] == cs[i]){
                    count = isPalindrome(cs, j, i)? count + 1 : count;
                }
            }
        }
        return count;
    }

    // 判断是否是回文串
    private boolean isPalindrome(char[] cs, int left, int right){
        if (left >= right){
            return true;
        }
        if (cs[left] != cs[right])
            return false;
        return isPalindrome(cs, left+1, right -1);
    } 
}

Solution

动态规划

class Solution {
    public int countSubstrings(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        int count = 0;
        for (int i = 0; i < s.length(); i ++){
            for (int j = 0; j <= i; j ++){
                if ((s.charAt(i) == s.charAt(j)) && (i - j < 2 || dp[j+1][i-1])){
                    dp[j][i] = true;
                    count ++;
                }
            }
        }
        return count;
    }
}