LeetCode第647題---回文子列の個数

回文子列
文字列を指定すると、この文字列に何個の返信サブ列があるかを計算します.異なる開始位置または終了位置を持つサブストリングは、同じ文字で構成されていても異なるサブストリングとしてカウントされます.例1:入力:「abc」出力:3解釈:3つの回文子列:「a」,「b」,「c」.例2:入力:「aaa」出力:6説明:6個の回文子列:「a」,「a」,「a」,「aaa」,「aaa」,「aaa」,「aaa」.
注意:入力した文字列の長さは1000を超えません.リンク:https://leetcode-cn.com/problems/palindromic-substrings

暴力解法の考え方:すべてのサブ文字列を遍歴し、回文かどうかを判断し、個数

を計算する.

動的計画法の構想:すべてのサブ文字列を遍歴し、すべてのサブ文字列が回文列であるかどうかを記憶する.すべてのサブ文字列を巡回し、もしそうであれば1を加算します.

/**
 *     ，               ，    
 */

public class Solution2 {
    public int countSubstrings(String s) {
        int count = 0;
        int length = s.length();
        boolean[][] dp = new boolean[length][length];
        for (int i = length - 1; i >= 0; i--) {    //  ，    ，     
            for (int j = i; j <= length - 1; j++) {  //  
                dp[i][j] = s.charAt(i) == s.charAt(j);
                if (i + 1 <= j - 1) {
                    dp[i][j] = dp[i + 1][j - 1] && dp[i][j];
                }
            }
        }
        //        ，       1
        for (int m = 1; m <= length; m++) {
            for (int k = 0; k <= length - m; k++) {
                if (dp[k][k + m - 1]) {
                    count++;
                }
            }
        }
        return count;
    }
}