Skip to content

1745. Palindrome Partitioning IV

Description

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.

Solutions

Solution 1: Dynamic Programming

Thinking

Split the string into three palindromes. Checking each candidate split from scratch is \(O(n^3)\) palindrome tests. \(n\) can be a few hundred, so precompute palindromes.

\(f[i][j]\) is whether \(s[i..j]\) is a palindrome. After filling it by interval length, try two cuts; the total is \(O(n^2)\).

We define \(f[i][j]\) to indicate whether the substring of \(s\) from the \(i\)-th character to the \(j\)-th character is a palindrome, initially \(f[i][j] = \textit{true}\).

Then we can calculate \(f[i][j]\) using the following state transition equation:

\[ f[i][j] = \begin{cases} \textit{true}, & \text{if } s[i] = s[j] \text{ and } (i + 1 = j \text{ or } f[i + 1][j - 1]) \\ \textit{false}, & \text{otherwise} \end{cases} \]

Since \(f[i][j]\) depends on \(f[i + 1][j - 1]\), we need to enumerate \(i\) from large to small and \(j\) from small to large, so that when calculating \(f[i][j]\), \(f[i + 1][j - 1]\) has already been calculated.

Next, we enumerate the right endpoint \(i\) of the first substring and the right endpoint \(j\) of the second substring. The left endpoint of the third substring can be enumerated in the range \([j + 1, n - 1]\), where \(n\) is the length of the string \(s\). If the first substring \(s[0..i]\), the second substring \(s[i+1..j]\), and the third substring \(s[j+1..n-1]\) are all palindromes, then we have found a feasible partitioning scheme and return \(\textit{true}\).

After enumerating all partitioning schemes, if no valid partitioning scheme is found, return \(\textit{false}\).

Time complexity is \(O(n^2)\), and space complexity is \(O(n^2)\). Where \(n\) is the length of the string \(s\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def checkPartitioning(self, s: str) -> bool:
        n = len(s)
        f = [[True] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                f[i][j] = s[i] == s[j] and (i + 1 == j or f[i + 1][j - 1])
        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                if f[0][i] and f[i + 1][j] and f[j + 1][-1]:
                    return True
        return False

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean checkPartitioning(String s) {
        int n = s.length();
        boolean[][] f = new boolean[n][n];
        for (var g : f) {
            Arrays.fill(g, true);
        }
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                f[i][j] = s.charAt(i) == s.charAt(j) && (i + 1 == j || f[i + 1][j - 1]);
            }
        }
        for (int i = 0; i < n - 2; ++i) {
            for (int j = i + 1; j < n - 1; ++j) {
                if (f[0][i] && f[i + 1][j] && f[j + 1][n - 1]) {
                    return true;
                }
            }
        }
        return false;
    }
}

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func checkPartitioning(s string) bool {
    n := len(s)
    f := make([][]bool, n)
    for i := range f {
        f[i] = make([]bool, n)
        for j := range f[i] {
            f[i][j] = true
        }
    }
    for i := n - 1; i >= 0; i-- {
        for j := i + 1; j < n; j++ {
            f[i][j] = s[i] == s[j] && (i+1 == j || f[i+1][j-1])
        }
    }
    for i := 0; i < n-2; i++ {
        for j := i + 1; j < n-1; j++ {
            if f[0][i] && f[i+1][j] && f[j+1][n-1] {
                return true
            }
        }
    }
    return false
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function checkPartitioning(s: string): boolean {
    const n = s.length;
    const f: boolean[][] = Array.from({ length: n }, () => Array(n).fill(true));
    for (let i = n - 1; i >= 0; --i) {
        for (let j = i + 1; j < n; ++j) {
            f[i][j] = s[i] === s[j] && f[i + 1][j - 1];
        }
    }
    for (let i = 0; i < n - 2; ++i) {
        for (let j = i + 1; j < n - 1; ++j) {
            if (f[0][i] && f[i + 1][j] && f[j + 1][n - 1]) {
                return true;
            }
        }
    }
    return false;
}

Comments