LeetCode 647. 回文子串

原题链接：. - 力扣（LeetCode）

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

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

示例 1：

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

示例 2：

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

提示：

• 1 <= s.length <= 1000
• s 由小写英文字母组成

思路：

本题可采用动态规划解决。dp[ i ][ j ] 为 true 则表示 s 中 下标 i ~ j 的字符串是回文子字符串。

递推公式推导如下：当 s.charAt( i )  != s.charAt( j ) 时，dp[ i ][ j ] 为 false。 当 s.charAt( i ) == s.charAt( j ) 时，此时 分为三种情况：一： i==j，这时说明 i 和 j 指向的是同一个字符 a，可以算作回文子字符串，因此 dp[ i ][ j ] = true；二：j - i == 1，这时说明 i 和 j 前后相邻，比如 aa，这时也是回文子字符串，因此 dp[ i ][ j ] = true；三：j - i >= 2 ，这时候需要判断 i+1 到 j-1 是否为回文子字符串，即 dp[ i+1 ][ j-1 ] 是否为 true，如果为 true，则说明 i ~ j 也是回文子字符串，即 dp[ i ][ j ] = true。如下所示： 

初始化：初始全初始化为 false。遍历顺序：由于 dp[ i ][ j ] 需要依赖 dp[ i +1 ][ j-1 ]，因此遍历顺序应该是从下往上，从左往右。

代码：

class Solution {
    public int countSubstrings(String s) {
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        /**dp[i][j]为true则表示下标i~j的s部分为回文子串
         */
        int result = 0;
        for(int i=len-1;i>=0;i--){
            for(int j=i;j<len;j++){
                if(s.charAt(j)==s.charAt(i)){
                    if(j-i<=1){
                        result++;
                        dp[i][j]=true;
                    }
                    else if(dp[i+1][j-1]){
                        result++;
                        dp[i][j]=true;
                    }
                }
            }
        }
        return result;
    }
}

参考：代码随想录