Given a string s, return true if it is possible to split the string s into three non-empty palindromic substrings. Otherwise, return false.
A string is said to be palindrome if it the same string when reversed.
Example 1:
Input: s = "abcbdd"
Output: true
Explanation: "abcbdd" = "a" + "bcb" + "dd", and all three substrings are palindromes.
Example 2:
Input: s = "bcbddxy"
Output: false
Explanation: s cannot be split into 3 palindromes.
Constraints:
3 <= s.length <= 2000
s consists only of lowercase English letters.
Solution:
use dp[][] to store whether substring[i, j] is palindrome
class Solution {
public boolean checkPartitioning(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
for (int len = 1; len <= n; len ++) {
for (int i = 0; i + len <= n; i ++) {
int j = i + len - 1;
if (i == j) {
dp[i][j] = true;
} else if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = (i + 1 == j) ? true : dp[i + 1][j - 1];
}
}
}
// for (boolean[] d: dp) System.out.println(Arrays.toString(d));
for (int i = 1; i <= n - 2; i ++) {
for (int j = i; j <= n - 2; j ++) {
if (dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1]) {
return true;
}
}
}
return false;
}
}