説明

小文字のアルファベット文字列 s が与えられた場合、 s の回文部分文字列の数を返します.

制約:

1 ≤ n ≤ 1,000 n は s の長さです

例1

入力

s = "tacocat"

出力

10

説明

The palindromic substrings are:

"t"
"a"
"c"
"o"
"c"
"a"
"t"
"coc"
"acoca"
"tacocat"

直感

DP[i][j] は、substring(i,j) が回文文字列の場合を意味します

の場合 i==j -> dp[i][j] = true ;

の場合 i!=j -> dp[i][j] = dp[i+1][j-1] && char[i]==char[j]

詳細

init dp array with false : boolean[][] dp = new boolean[length][length] ;

初期化 count = 0 ;

start を end と比較します.
◦ start == end : dp[start][end] = true ;
◦ chars[start] と chars[end] を比較

実装

import java.util.*;

class Solution {
    public int solve(String s) {
        int length = s.length();
        boolean[][] dp = new boolean[length][length];
        int count = 0;
        for (int end = 0; end < length; end++) {
            for (int start = 0; start <= end; start++) {
                if (start == end) {
                    dp[start][end] = true;
                    count++;
                } else {
                    if (s.charAt(start) == s.charAt(end)) {
                        if (end - start == 1 || dp[start + 1][end - 1]) {
                            dp[start][end] = true;
                            count++;
                        }
                    }
                }
            }
        }
        return count;
    }
}

時間の複雑さ

時間: O(n^2)

スペース: O(n^2)