132. Palindrome Partitioning II

LeetCode problem link (opens new window)

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example 1:

Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Example 2:
Input: s = "a"
Output: 0

Example 3:
Input: s = "ab"
Output: 1

Constraints:

• 1 <= s.length <= 2000
• s consists of lowercase English letters only.

Thought Process

When we discussed the backtracking series, we covered this problem: 0131.Palindrome Partitioning (opens new window).

In fact, this problem can also be solved using backtracking, but it would time out! (Through memoized backtracking, it can also pass, interested readers can explore this method on their own).

Let's talk about how to solve this problem using dynamic programming.

Regarding palindromic substrings, there are two essential problems that must be mastered.

• Dynamic Programming: 0647.Palindromic Substrings (opens new window)
• 5. Longest Palindromic Substring is very similar to 0647.Palindromic Substrings

These two problems form the basis of palindromic substrings, and this problem will also utilize related concepts.

Analyzing the five steps of dynamic programming:

1. Define the dp array and its meaning

dp[i]: The minimum cut needed for the substring from index 0 to i to partition it into palindromic substrings.

2. Formulate the recurrence relation

Let’s see how to derive dp[i].

If we want to cut the string ranging from 0 to i, the cut point could be j.

If the substring from [j + 1, i] is a palindrome, then dp[i] equals dp[j] + 1.

Some might wonder why we only check if [j + 1, i] is a palindrome without checking [0, j].

Let’s revisit the definition of dp[i]: The minimum cuts needed for a palindromic partition of the range [0, i].

We already know the minimum cut count for [0, j], which is dp[j].

We have now found the recurrence relation: when the cut point j is between 0 and i, dp[i] = dp[j] + 1.

Since this problem is about finding the minimum cut count, we should choose the minimal dp[i] when iterating j.

Hence the recurrence relation is: dp[i] = min(dp[i], dp[j] + 1);

Note that it's not about comparing dp[j] + 1 with dp[i], but taking the minimum of dp[i] during the iteration over j!

We can derive dp[j] + 1 when the substring [j + 1, i] is a palindrome.

3. Initialize the dp array

First, let's consider what dp[0] should be.

dp[i]: denotes the minimum cuts needed for a palindromic partition of the range [0, i].

Thus, dp[0] must be 0 because a single character string requires 0 cuts. This is quite intuitive.

Now let's consider how non-zero indices should be initialized for dp[i].

In the recurrence relation dp[i] = min(dp[i], dp[j] + 1), we see we need to take the minimum of dp[i].

So non-zero indices should be initialized to a large number, so when applying the recurrence relation, the initial values don't overwrite our results!

If non-zero indices were initialized to 0, the recurrence relation would result in all zeroes.

Non-zero indices of dp[i] should be initialized to a maximum number.

Here’s the code for initialization:

vector<int> dp(s.size(), INT_MAX);
dp[0] = 0;

Alternatively, we can initialize based on the definition of dp[i]; the maximum dp[i] can be is i, which means separating every character out.

So the initialization could also be:

vector<int> dp(s.size());
for (int i = 0; i < s.size(); i++) dp[i] = i;

4. Determine the iteration order

According to the recurrence relation: dp[i] = min(dp[i], dp[j] + 1);

j is between 0 and i, so the outer for-loop must iterate over i. Here, j must be inside the outer loop, so dp[i] can be derived from already computed dp[j].

The code looks like this:

for (int i = 1; i < s.size(); i++) {
    if (isPalindromic[0][i]) { // Check if it's a palindromic substring
        dp[i] = 0;
        continue;
    }
    for (int j = 0; j < i; j++) {
        if (isPalindromic[j + 1][i]) {
            dp[i] = min(dp[i], dp[j] + 1);
        }
    }
}

You will notice a function isPalindromic in the code, which is a 2D array isPalindromic[i][j], recording whether [i, j] is a palindrome.

How is this isPalindromic[i][j] generated?

This code is essentially the same as that in these two problems:

• 0647.Palindromic Substrings (opens new window)
• 5. Longest Palindromic Substring

So let's first use a 2D array to store the palindromic status of the entire string.

The code is as follows:

vector<vector<bool>> isPalindromic(s.size(), vector<bool>(s.size(), false));
for (int i = s.size() - 1; i >= 0; i--) {
    for (int j = i; j < s.size(); j++) {
        if (s[i] == s[j] && (j - i <= 1 || isPalindromic[i + 1][j - 1])) {
            isPalindromic[i][j] = true;
        }
    }
}

5. Example to derive the dp array

Take the input: "aabc" as an example:

With the above analysis, here’s the code:

class Solution {
public:
    int minCut(string s) {
        vector<vector<bool>> isPalindromic(s.size(), vector<bool>(s.size(), false));
        for (int i = s.size() - 1; i >= 0; i--) {
            for (int j = i; j < s.size(); j++) {
                if (s[i] == s[j] && (j - i <= 1 || isPalindromic[i + 1][j - 1])) {
                    isPalindromic[i][j] = true;
                }
            }
        }
        // Initialization
        vector<int> dp(s.size(), 0);
        for (int i = 0; i < s.size(); i++) dp[i] = i;

        for (int i = 1; i < s.size(); i++) {
            if (isPalindromic[0][i]) {
                dp[i] = 0;
                continue;
            }
            for (int j = 0; j < i; j++) {
                if (isPalindromic[j + 1][i]) {
                    dp[i] = min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[s.size() - 1];

    }
};

Versions in Other Languages

Java

class Solution {

    public int minCut(String s) {
        if(null == s || "".equals(s)){
            return 0;
        }
        int len = s.length();
        // 1.
        // Record whether the substring [i..j] is a palindrome
        boolean[][] isPalindromic = new boolean[len][len];
        // From bottom to top, left to right
        for(int i = len - 1; i >= 0; i--){
            for(int j = i; j < len; j++){
                if(s.charAt(i) == s.charAt(j)){
                    if(j - i <= 1){
                        isPalindromic[i][j] = true;
                    } else{
                        isPalindromic[i][j] = isPalindromic[i + 1][j - 1];
                    }
                } else{
                    isPalindromic[i][j] = false;
                }
            }
        }

        // 2.
        // dp[i] denotes the minimum cut needed for the range [0..i]
        int[] dp = new int[len];
        for(int i = 0; i < len; i++){
            // Initially consider the worst case. 1 character requires 0 cuts, length requires len - 1 cuts
            dp[i] = i;
        }

        for(int i = 1; i < len; i++){
            if(isPalindromic[0][i]){
                // s[0..i] is a palindrome, so dp[i] = 0, no cuts needed
                dp[i] = 0;
                continue;
            }
            for(int j = 0; j < i; j++){
                // Follow the thought process, use "ababa" as an example, and write down the isPalindromic array, then perform calculations
                if(isPalindromic[j + 1][i]){
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[len - 1];
    }
}

Python

class Solution:
    def minCut(self, s: str) -> int:

        isPalindromic=[[False]*len(s) for _ in range(len(s))]

        for i in range(len(s)-1,-1,-1):
            for j in range(i,len(s)):
                if s[i]!=s[j]:
                    isPalindromic[i][j] = False
                elif  j-i<=1 or isPalindromic[i+1][j-1]:
                    isPalindromic[i][j] = True

        # print(isPalindromic)
        dp=[sys.maxsize]*len(s)
        dp[0]=0

        for i in range(1,len(s)):
            if isPalindromic[0][i]:
                dp[i]=0
                continue
            for j in range(0,i):
                if isPalindromic[j+1][i]==True:
                    dp[i]=min(dp[i], dp[j]+1)
        return dp[-1]

Go

func minCut(s string) int {
    isValid := make([][]bool, len(s))
    for i := 0; i < len(isValid); i++ {
        isValid[i] = make([]bool, len(s))
        isValid[i][i] = true
    }
    for i := len(s) - 1; i >= 0; i-- {
        for j := i + 1; j < len(s); j++ {
            if s[i] == s[j] && (isValid[i + 1][j - 1] || j - i == 1) {
                isValid[i][j] = true
            }
        }
    }

    dp := make([]int, len(s))
    for i := 0; i < len(s); i++ {
        dp[i] = math.MaxInt
    }
    for i := 0; i < len(s); i++ {
        if isValid[0][i] {
            dp[i] = 0
            continue
        }
        for j := 0; j < i; j++ {
            if isValid[j + 1][i] {
                dp[i] = min(dp[i], dp[j] + 1)
            }
        }
    }
    return dp[len(s) - 1]
}

func min(i, j int) int {
    if i < j {
        return i
    } else {
        return j
    }
}

JavaScript

var minCut = function(s) {
    const len = s.length;
    // Use 2D array isPalindromic to store the palindromic status of the entire string
    const isPalindromic = new Array(len).fill(false).map(() => new Array(len).fill(false));
    for(let i = len - 1; i >= 0; i--){
        for(let j = i; j < len; j++){
            if(s[i] === s[j] && (j - i <= 1 || isPalindromic[i + 1][j - 1])){
                isPalindromic[i][j] = true;
            }
        }
    }
    // dp[i]: the minimum cut needed for the palindrome partitioning of the range [0, i]
    const dp = new Array(len).fill(0);
    for(let i = 0; i < len; i++) dp[i] = i; // Initializing dp[i] to its maximum value, which means separating every character individually
    for(let i = 1; i < len; i++){
        if(isPalindromic[0][i]){ // Check if it's a palindromic substring
            dp[i] = 0;
            continue;
        }
        /* 
        If we want to cut the string ranging from 0 to i, the cut point could be j.
        If the substring from [j + 1, i] is a palindrome, then dp[i] equals dp[j] + 1.
        Some might wonder why we only check if [j + 1, i] is a palindrome without checking [0, j].
        Let’s revisit the definition of dp[i]: The minimum cuts needed for a palindromic partition of the range [0, i].
        We already know the minimum cut count for [0, j], which is dp[j].
        We have now found the recurrence relation: when the cut point j is between 0 and i, dp[i] = dp[j] + 1;
        Since this problem is about finding the minimum cut count, we should choose the minimal dp[i] when iterating j. dp[i] = Math.min(dp[i], dp[j] + 1);
         */
        for(let j = 0; j < i; j++){
            if(isPalindromic[j + 1][i]){
                dp[i] = Math.min(dp[i], dp[j] + 1);
            }
        }
    }
    return dp[len - 1];
};