Palindrome Partitioning Ii

Solution For Palindrome Partitioning Ii

Problem Statement:

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 lower-case English letters only.

Solution:

Approach:

The problem requires us to find the minimum number of cuts required to partition a string s into palindromic substrings. This can be done by using Dynamic Programming.

We can use the following approach to solve this problem:

Step 1: Initialize a one-dimensional DP array dp of size n + 1, where n is the length of the string. Here dp[i] will store the minimum number of cuts required to partition the string s[0..i-1] into palindromic substrings.

Step 2: Initialize each element of the array as its index value.

Step 3: Traverse the array from the second character to the end of the string.

Step 4: For each character i, traverse the array from the start to i.

Step 5: If the current substring s[j..i] is a palindrome, update the minimum cuts required to partition the string s[0..i-1].

The minimum cuts required will be dp[j] + 1, where dp[j] is the minimum number of cuts required to partition the string s[0..j-1] into palindromic substrings, and the additional cut 1 is made to include the current palindrome string s[j..i]. We take minimum of all such values as we want the minimum number of cuts possible.

Step 6: Return dp[n] – 1, as we’re working on 0-based indexing and this will be the final answer.

Code:

The code implementation of the above approach is given below:

class Solution {
public:
int minCut(string s) {
int n = s.length();

    vector<int> dp(n + 1, 0);
    for(int i = 0;i <= n;i++)
        dp[i] = i - 1;

    for(int i = 1;i < n;i++) {
        for(int j = 0;j <= i;j++) {
            if(isPalindrome(s, j, i)) {
                dp[i + 1] = min(dp[i + 1], dp[j] + 1);
            }
        }
    }
    return dp[n];
}

private:
bool isPalindrome(string s, int i, int j) {
while(i < j) {
if(s[i] != s[j])
return false;
i++;
j–;
}
return true;
}
};

Time Complexity:

The time complexity of the solution is O(n^2) as we’re traversing two loops for i and j, and checking palindrome string takes O(n).

Space Complexity:

The space complexity of the solution is O(n), as we’re using a dp array of size n.

Step by Step Implementation For Palindrome Partitioning Ii

public class Solution {
    public int minCut(String s) {
        //check null
        if(s == null || s.length() == 0){
            return 0;
        }
        //get length
        int len = s.length();
        //create an array to store whether the string from ith to jth is palindrome
        boolean[][] dp = new boolean[len][len];
        //create an array to store the minCut from ith to jth
        int[] cut = new int[len];
        
        for(int j = 0; j < len; j++){
            cut[j] = j; //set the max # of cut as j
            for(int i = 0; i <= j; i++){
                if(s.charAt(i) == s.charAt(j) && (j-i <= 1 || dp[i+1][j-1])){
                    dp[i][j] = true;
                    //if need to cut, add 1
                    if(i > 0){
                        cut[j] = Math.min(cut[j], cut[i-1] + 1);
                    }else{
                        //if [0...j] is palindrome, no need to cut
                        cut[j] = 0;
                    }
                }
            }
        }
        return cut[len-1];
    }
}
def minCut(self, s):
        # write your code here
        if s is None or len(s) == 0:
            return 0
        n = len(s)
        is_palindrome = [[False for i in range(n)] for j in range(n)]
        for i in range(n):
            is_palindrome[i][i] = True
        for i in range(n-1):
            is_palindrome[i][i+1] = (s[i] == s[i+1])
        for length in range(2, n):
            for start in range(n-length):
                is_palindrome[start][start+length] = is_palindrome[start+1][start+length-1] and s[start] == s[start+length]
        cuts = [i-1 for i in range(n+1)]
        for i in range(n):
            for j in range(i, -1, -1):
                if is_palindrome[j][i]:
                    cuts[i+1] = min(cuts[i+1], cuts[j] + 1)
        return cuts[n]
var minCut = function(s) {
    let n = s.length;
    let cut = Array(n).fill(0);
    let isPal = Array(n).fill(Array(n).fill(false));
    
    for (let j = 0; j < n; j++) {
        cut[j] = j; // set maximum # of cuts to be j
        for (let i = 0; i <= j; i++) {
            if (s[i] == s[j] && (j - i <= 1 || isPal[i+1][j-1])) {
                isPal[i][j] = true;
                // if [i,j] is a palindrome, no need to cut
                if (i == 0) { 
                    cut[j] = 0;
                } else {
                    cut[j] = Math.min(cut[j], cut[i-1] + 1);
                }
            }
        }
    }
    
    return cut[n-1];
};
class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector cut(n+1, 0);  // number of cuts for the first k characters
        for (int i = 0; i <= n; i++) cut[i] = i-1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; i-j >= 0 && i+j < n && s[i-j]==s[i+j] ; j++) // odd length palindrome
                cut[i+j+1] = min(cut[i+j+1],1+cut[i-j]);

            for (int j = 1; i-j+1 >= 0 && i+j < n && s[i-j+1]==s[i+j]; j++) // even length palindrome
                cut[i+j+1] = min(cut[i+j+1],1+cut[i-j+1]);
        }
        return cut[n];
    }
};
public class Solution {
    public int MinCut(string s) {
        if (string.IsNullOrEmpty(s)) return 0;
        int n = s.Length;
        // dp[i,j] represents the min cut needed for substring s[i...j]
        int[,] dp = new int[n,n];
        // isPal[i,j] represents whether substring s[i...j] is a palindrome
        bool[,] isPal = new bool[n,n];
        for (int j = 0; j < n; j++) {
            dp[j,j] = 0;
            isPal[j,j] = true;
            for (int i = j-1; i >= 0; i--) {
                if (s[i] == s[j] && (j-i < 2 || isPal[i+1,j-1])) {
                    isPal[i,j] = true;
                    dp[i,j] = 0;
                } else {
                    isPal[i,j] = false;
                    dp[i,j] = int.MaxValue;
                    for (int k = i; k < j; k++) {
                        dp[i,j] = Math.Min(dp[i,j], dp[i,k]+dp[k+1,j]+1);
                    }
                }
            }
        }
        return dp[0,n-1];
    }
}
Scroll to Top

Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]