LeetCode 1745. Palindrome Partitioning IV Solution in Java, C++, Python & More | Explanation + Code

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

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] = true.

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

f[i][j] = \begin{cases} true, & if s[i] = s[j] and (i + 1 = j or f[i + 1][j - 1]) \ false, & 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 true.

After enumerating all partitioning schemes, if no valid partitioning scheme is found, return false.

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

PythonJavaC++GoTypeScript

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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)

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; }(code-box)