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"

1. 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]

2. Iterate through all possible partitions i and j.
   • For example, when i = 0 and j = 1, the partitions would be: "a", "b", "cbdd".
   • We'll then check if all three substrings are palindromes using isPalindrome function which uses the dp array to store already computed answers.
3. 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.