https://leetcode.com/problems/palindrome-partitioning-iv/ from tcs

Thinking process:

Check the constraint. The input length is at most 2000, which means we can use at most O(N^2) algorithm. If we just brute force the two split positions and check if the three substrings are palindrome, the time complexity will be O(N^3) (N^2 combinations of the split positions, and O(N) time to check if all three substrings are palindrome).

With the observations above, we just need to reduce the checking time to O(1) then we’re done. This leads us to think about the dp solution. We can define dp[i][j] as true if s[i] to s[j] (inclusive) is a palindrome, and then pre-compute the dp table in O(N^2) time.

How do we check if s[i] to s[j] is a palindrome? We have two conditions: 1. s[i] == s[j] 2. dp[i+1][j-1] is true. Just like the green part and yellow part above. We also know every substring with length equal to 1 is a palindrome, so in my code, I init all dp[i][i] to be true.

Finally, just expand dp[i][j] by the length. We first calculate all dp[i][j] with length equal to 2, and then 3 … etc. We can complete this in O(N^2) time. After this pre-computing, we can iterate through all N^2 combination of split positions and check if all three substrings are palindrome in O(1) time.

Here is the code.

 1class Solution {
 2public:
 3    bool checkPartitioning(string s) {
 4        int N = s.size();
 5        vector<vector<bool>> dp(N, vector<bool>(N));
 6        for (int i=0; i<N; i++) dp[i][i] = true;
 7        for (int l=2; l<=N; l++) {
 8            for (int i=0; i+l<=N; i++) {
 9                int j = i + l - 1;
10                dp[i][j] = (s[i] == s[j] and ((i+1 <= j-1) ? dp[i+1][j-1] : true));
11            }
12        }
13        for (int i=1; i<N-1; i++) {
14            for (int j=i+1; j<N; j++) {
15                if (dp[0][i-1] and dp[i][j-1] and dp[j][N-1]) {
16                    return true;
17                }
18            }
19        }
20        return false;
21    }
22};