Problem
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 <= 2000s consists only of lowercase English letters.
Solution
class Solution {
public boolean checkPartitioning(String s) {
final int len = s.length();
char[] ch = s.toCharArray();
int[] dp = new int[len + 1];
dp[0] = 0x01;
for (int i = 0; i < len; i++) {
for (int l : new int[] {i - 1, i}) {
int r = i;
while (l >= 0 && r < len && ch[l] == ch[r]) {
dp[r + 1] |= dp[l] << 1;
l--;
r++;
}
}
}
return (dp[len] & 0x08) == 0x08;
}
}
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).