43 lines
1.2 KiB
Java
43 lines
1.2 KiB
Java
import java.util.*;
|
|
|
|
public class _1509 {
|
|
public static void main(String[] args) {
|
|
Scanner sc = new Scanner(System.in);
|
|
String str = sc.nextLine();
|
|
sc.close();
|
|
|
|
int L = str.length();
|
|
boolean[][] isPalindrome = new boolean[L][L];
|
|
for(int i=0; i<L; i++) {
|
|
isPalindrome[i][i] = true;
|
|
|
|
if(i < L-1 && str.charAt(i) == str.charAt(i+1)) {
|
|
isPalindrome[i][i+1] = true;
|
|
}
|
|
}
|
|
|
|
for(int len=3; len<=L; len++) {
|
|
for(int start=0; start <= L - len; start++) {
|
|
int end = start + len - 1;
|
|
|
|
if(str.charAt(start) == str.charAt(end) && isPalindrome[start+1][end-1]) {
|
|
isPalindrome[start][end] = true;
|
|
}
|
|
}
|
|
}
|
|
|
|
int[] dp = new int[L];
|
|
Arrays.fill(dp, Integer.MAX_VALUE);
|
|
|
|
for(int end=0; end<L; end++) {
|
|
for(int start=0; start<=end; start++) {
|
|
if(isPalindrome[start][end]) {
|
|
if(start==0) dp[end] = 1;
|
|
else dp[end] = Math.min(dp[end], dp[start-1] + 1);
|
|
}
|
|
}
|
|
}
|
|
|
|
System.out.println(dp[L-1]);
|
|
}
|
|
} |