Skip to content

Latest commit

 

History

History

1745

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 

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.

Related Topics:
String, Dynamic Programming

Similar Questions:

Solution 1. Rolling Hash

// OJ: https://leetcode.com/problems/palindrome-partitioning-iv/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(N^2)
class Solution {
public:
    bool checkPartitioning(string s) {
        unsigned N = s.size(), h[2001][2001] = {}, rh[2001][2001] = {}, d = 16777619;
        for (int i = 0; i < N; ++i) {
            int hash = 0;
            for (int j = i; j < N; ++j) {
                hash = hash * d + s[j] - 'a';
                h[i][j] = hash;
            }
        }
        reverse(begin(s), end(s));
        for (int i = 0; i < N; ++i) {
            int hash = 0;
            for (int j = i; j < N; ++j) {
                hash = hash * d + s[j] - 'a';
                rh[N - j - 1][N - i - 1] = hash;
            }
        }
        for (int i = 0; i < N; ++i) { // first part [0,i]
            if (h[0][i] != rh[0][i]) continue;
            for (int j = i + 1; j < N - 1; ++j) { // second part [i+1,j], last part [j+1,N-1]
                if (h[i + 1][j] == rh[i + 1][j] && h[j + 1][N - 1] == rh[j + 1][N - 1]) return true;
            }
        }
        return false;
    }
};

Solution 2. DP

Let dp[i][j] be whether substring s[i..j] is a palindrome.

dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1]
dp[i][i] = true 
// OJ: https://leetcode.com/problems/palindrome-partitioning-iv/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(N^2)
class Solution {
public:
    bool checkPartitioning(string s) {
        int N = s.size(), dp[2001][2001] = {};
        for (int i = N - 1; i >= 0; --i) { // substring [i,j]
            for (int j = i; j < N; ++j) {
                if (i == j) dp[i][j] = true;
                else if (i + 1 == j) dp[i][j] = s[i] == s[j];
                else dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1];
            }
        }
        for (int i = 0; i < N; ++i) { // first part [0,i]
            for (int j = i + 1; j < N - 1; ++j) { // second part [i+1,j], last part [j+1,N-1]
                if (dp[0][i] && dp[i + 1][j] && dp[j + 1][N - 1]) return true;
            }
        }
        return false;
    }
};