Monday, September 7, 2020

Palindrome Partitioning II | Dynamic Programing | O(N^2) | C++

 


Problem Description:

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

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


Input Format:

The first and the only argument contains the string A.

Output Format:

Return an integer, representing the answer as described in the problem statement.

Constraints:

1 <= length(A) <= 501

Examples:

Input 1:
    A = "aba"

Output 1:
    0

Explanation 1:
    "aba" is already a palindrome, so no cuts are needed.

Input 2:
    A = "aab"
    
Output 2:
    1

Explanation 2:
    Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.


Approach:

This problem is a variation of Matrix Chain Multiplication problem. If the string is a palindrome, then we simply return 0. Else, like the Matrix Chain Multiplication problem, we try making cuts at all possible places, recursively calculate the cost for each cut and return the minimum value.

Let the given string be "s" and mincut() be the function that returns the fewest cuts needed for palindrome partitioning. following is the optimal substructure property.

Using Recursion

// i is the starting index and j is the ending index. i must be passed as 0 and j as n-1
mincut(str, i, j) = 0 if i == j. // When string is of length 1.
mincut(str, i, j) = 0 if str[i..j] is palindrome.

// If none of the above conditions is true, then mincut(str, i, j) can be 
// calculated recursively using the following formula.
mincut(str, i, j) = Min { mincut(str, i, k) + 1 +
                                 mincut(str, k+1, j) } 
                           where k varies from i to j-1


Using Memorization to solve this problem.
The basic idea is to cache the intermittent results calculated in recursive functions. We can put these results into a hashmap/unordered_map/Matrix.

Problem Solution in C++ Programming Language:

code:
#include<bits/stdc++.h>
using namespace std;

bool ispali(string s,int i,int j)
{
    if(i>=j) return true;
    while(i<j)
    {
        if(s[i]!=s[j])  return false;
        i++;
        j--;
    }
    return true;
}
int solve(string s,int i,int j,vector<vector<int>> &dp)
{
    if(i>j) return 0;
    if(dp[i][j]!=-1return dp[i][j];
    if(i==j) return dp[i][j]=0;
    
    if(ispali(s,i,j))   return dp[i][j]=0;
    
    int mn=INT_MAX;
    
    for(int k=i;k<j;k++)
    {
        int l=INT_MAX;
        int r=INT_MAX;
        
        if(dp[i][k]!=-1) l=dp[i][k];
        else l=solve(s,i,k,dp);
        if(dp[k+1][j]!=-1) r=dp[k+1][j];
        else r=solve(s,k+1,j,dp);
        
        mn=min(mn,l+r+1);
    }
    return dp[i][j]=mn;
}

int minCut(string A
{
    int n=A.size();
    vector<vector<int>> dp(n+1,vector<int> (n+1,-1));
    return solve(A,0,n-1,dp);
}

int main()
{
    string s;
    s="ababbbabbababa";
    cout<<minCut(s);
    return 0;
}

Time Complexity: O(n^2)

Space Complexity: O(n^2)


Please share your reviews.

thanks for reading.👍😊

If you like the solution please share with your friends.

and for more dynamic programming question for interview preparation.

No comments:

Post a Comment

Please do not enter any spam link in the comment box