_1745.java

packagecom.fishercoder.solutions.secondthousand;

publicclass_1745 {
publicstaticclassSolution1 {
/*
 * credit: https://leetcode.com/problems/palindrome-partitioning-iv/discuss/1042910/Java-Detailed-Explanation-DP-O(N2)
 *
 * check whether substring(i, j) is a palindrome becomes checking whether substring(i + 1, j -1) is a palindrome
 *
 * How we build the dp array:
 * start from the top right of this square matrix
 */
publicbooleancheckPartitioning(Strings) {
intn = s.length();
boolean[][] dp = newboolean[n][n];
for (inti = n - 1; i >= 0; i--) {
for (intj = i; j < n; j++) {
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = (i + 1 <= j - 1) ? dp[i + 1][j - 1] : true;
 } else {
dp[i][j] = false;
 }
 }
 }
for (inti = 1; i < n - 1; i++) {
for (intj = i; j < n - 1; j++) {
if (dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1]) {
returntrue;
 }
 }
 }
returnfalse;
 }
 }
}