Leetcode 1745. Palindrome Partitioning IV
Problem 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 a palindrome if it is 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.
Approach
We are going to use dynamic programming to solve this problem.
The dynamic programming approach uses a 2D dp array such that dp[i][j]
is true if the substring s[i..j]
is palindrome.
To check for partitions, we will iterate through all possible partitions triplet of i
and j
where 0 <= i < n
and i+1 <= j < n
. If all three substrings: s[0..i]
, s[i+1..j]
and s[j+1..n-1]
are palindromes, then the string s
can be partitioned into 3 palindromes and we return true, otherwise false.
Example
Let's work through an example to demonstrate how the algorithm works:
Given string s = "abcbdd"
- Create a 2D dp array
dp
of size nxn, initialized with -1.
1dp = [ 2 [-1, -1, -1, -1, -1, -1], 3 [-1, -1, -1, -1, -1, -1], 4 [-1, -1, -1, -1, -1, -1], 5 [-1, -1, -1, -1, -1, -1], 6 [-1, -1, -1, -1, -1, -1], 7 [-1, -1, -1, -1, -1, -1] 8]
- Iterate through all possible partitions
i
andj
.- For example, when
i = 0
andj = 1
, the partitions would be: "a", "b", "cbdd". - We'll then check if all three substrings are palindromes using
isPalindrome
function which uses thedp
array to store already computed answers.
- For example, when
- If a valid partition is found, return true. Otherwise, return false.
In this example, the valid partition is "a", "bcb", and "dd" with i = 0
and j = 2
. So, the function returns true.
Python Solution
1class Solution:
2 def checkPartitioning(self, s: str) -> bool:
3 n = len(s)
4 dp = [[-1 for _ in range(n)] for _ in range(n)]
5
6 def isPalindrome(i, j):
7 if i > j:
8 return 1
9 if dp[i][j] != -1:
10 return dp[i][j]
11 if s[i] == s[j]:
12 dp[i][j] = isPalindrome(i+1, j-1)
13 else:
14 dp[i][j] = 0
15 return dp[i][j]
16
17 for i in range(n):
18 for j in range(i+1, n):
19 if isPalindrome(0, i) and isPalindrome(i+1, j) and isPalindrome(j+1, n-1):
20 return True
21 return False
Java Solution
1class Solution {
2 public boolean checkPartitioning(String s) {
3 int n = s.length();
4 int[][] dp = new int[n][n];
5
6 for (int i = 0; i < n; ++i)
7 for (int j = 0; j < n; ++j)
8 dp[i][j] = -1;
9
10 for (int i = 0; i < n; ++i) {
11 for (int j = i + 1; j < n; ++j) {
12 if (isPalindrome(s, 0, i, dp) == 1 && isPalindrome(s, i + 1, j, dp) == 1 &&
13 isPalindrome(s, j + 1, n - 1, dp) == 1)
14 return true;
15 }
16 }
17
18 return false;
19 }
20
21 private int isPalindrome(String s, int i, int j, int[][] dp) {
22 if (i > j)
23 return 1;
24 if (dp[i][j] != -1)
25 return dp[i][j];
26 if (s.charAt(i) == s.charAt(j))
27 dp[i][j] = isPalindrome(s, i + 1, j - 1, dp);
28 else
29 dp[i][j] = 0;
30 return dp[i][j];
31 }
32}
JavaScript Solution
1class Solution {
2 checkPartitioning(s) {
3 const n = s.length;
4 const dp = Array.from({ length: n }, () => Array(n).fill(-1));
5
6 const isPalindrome = (i, j) => {
7 if (i > j) {
8 return 1;
9 }
10 if (dp[i][j] !== -1) {
11 return dp[i][j];
12 }
13 if (s.charAt(i) === s.charAt(j)) {
14 dp[i][j] = isPalindrome(i + 1, j - 1);
15 } else {
16 dp[i][j] = 0;
17 }
18 return dp[i][j];
19 };
20
21 for (let i = 0; i < n; ++i) {
22 for (let j = i + 1; j < n; ++j) {
23 if (isPalindrome(0, i) === 1 && isPalindrome(i + 1, j) === 1 && isPalindrome(j + 1, n - 1) === 1) {
24 return true;
25 }
26 }
27 }
28
29 return false;
30 }
31}
C++ Solution
1class Solution {
2public:
3 bool checkPartitioning(string s) {
4 int n = s.length();
5 vector<vector<int>> dp(n, vector<int>(n, -1));
6
7 for (int i = 0; i < n; ++i) {
8 for (int j = i+1; j < n; ++j) {
9 if (isPalindrome(s, 0, i, dp) == 1 && isPalindrome(s, i+1, j, dp) == 1 && isPalindrome(s, j+1, n-1, dp) == 1) {
10 return true;
11 }
12 }
13 }
14
15 return false;
16 }
17
18private:
19 int isPalindrome(const string& s, int i, int j, vector<vector<int>>& dp) {
20 if (i > j)
21 return 1;
22 if (dp[i][j] != -1)
23 return dp[i][j];
24 if (s[i] == s[j])
25 dp[i][j] = isPalindrome(s, i+1, j-1, dp);
26 else
27 dp[i][j] = 0;
28 return dp[i][j];
29 }
30};
C# Solution
1public class Solution {
2 public bool CheckPartitioning(string s) {
3 int n = s.Length;
4 int[][] dp = new int[n][];
5
6 for (int i = 0; i < n; ++i) {
7 dp[i] = new int[n];
8 for (int j = 0; j < n; ++j)
9 dp[i][j] = -1;
10 }
11
12 for (int i = 0; i < n; ++i) {
13 for (int j = i+1; j < n; ++j) {
14 if (isPalindrome(s, 0, i, dp) == 1 && isPalindrome(s, i+1, j, dp) == 1 && isPalindrome(s, j+1, n-1, dp) == 1) {
15 return true;
16 }
17 }
18 }
19
20 return false;
21 }
22
23 private int isPalindrome(string s, int i, int j, int[][] dp) {
24 if (i > j)
25 return 1;
26 if (dp[i][j] != -1)
27 return dp[i][j];
28 if (s[i] == s[j])
29 dp[i][j] = isPalindrome(s, i+1, j-1, dp);
30 else
31 dp[i][j] = 0;
32 return dp[i][j];
33 }
34}
All the code snippets provided above contain solutions to the given problem using the dynamic programming approach in different programming languages like Python, Java, JavaScript, C++, and C#. You can use any of these solutions based on your language of choice.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.