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.

Problem Link

Palindrome Partitioning II - LeetCode

Reference Videos

https://www.youtube.com/watch?v=qmTtAbOTqcg&ab_channel=Pepcoding

Code

// Using Memoization

class Solution{
public:
    int dp[501][501];
    int isP[501][501];
    int isPallindrome(string str,int i,int j) {
        
       if(i>=j)
       return isP[i][j] = 1;
       
       if(isP[i][j]!=-1)
       return isP[i][j];
       
       
       isP[i][j] = str[i]!=str[j] ? 0 : isPallindrome(str,i+1,j-1);
       
       return isP[i][j];
        
        
    }
    int palindromicPartition(string str)
    {
        memset(dp,-1,sizeof(dp));
        memset(isP,-1,sizeof(isP));
        int n = str.size();
        return topdownDP(str,0,n-1);
        
    }
    int topdownDP(string str,int i,int j) {
        
        if(i>=j||isPallindrome(str,i,j)==1)
        return dp[i][j] = 0;
        
        if(dp[i][j]!=-1)
        return dp[i][j];
        
        dp[i][j] = INT_MAX;
        
        for(int k=i;k<j;k++)
        dp[i][j] = min(dp[i][j],topdownDP(str,i,k)+topdownDP(str,k+1,j)+1);
        
        return dp[i][j];
    }
};
// Time Complexity : O(n^3),   Space Complexity : O(n^2)

//Using Bottom-Up DP

class Solution{
public:
    int palindromicPartition(string str)
    {
       int n = str.size();
       
       vector<vector<bool>> isP(n,vector<bool>(n,true));
       
       for(int gap=0;gap<n;gap++) {
           for(int i=0,j=gap;j<n;i++,j++) {
               
               if(i>=j)
               isP[i][j] = true;
               
               else
               isP[i][j] = str[i]!=str[j] ? false : isP[i+1][j-1];
           }
       }

       vector<vector<int>> dp(n,vector<int>(n));
       
       for(int gap=0;gap<n;gap++) {
           for(int i=0,j=gap;j<n;i++,j++) {
               
               if(i>=j)
               dp[i][j] = 0;
               
               else if(isP[i][j])
               dp[i][j] = 0;
               
               else
               {
                   dp[i][j] = INT_MAX;
                   for(int k=i;k<j;k++)
                   dp[i][j] = min(dp[i][j],1+dp[i][k]+dp[k+1][j]);
               }
           }
       }
       return dp[0][n-1];
    }
};
// Time Complexity : O(n^3),   Space Complexity : O(n^2)

// Time Optimized Bottom Up DP (LIS variant)

class Solution {
public:
    int minCut(string str) {
        
       int n = str.size();
       
       vector<vector<bool>> isP(n,vector<bool>(n,true));
       
       for(int gap=0;gap<n;gap++) {
           for(int i=0,j=gap;j<n;i++,j++) {
               
               if(i>=j)
               isP[i][j] = true;
               
               else
               isP[i][j] = str[i]!=str[j] ? false : isP[i+1][j-1];
           }
       }
 
       vector<int> dp(n);
       
       dp[0] = 0;
       
       for(int i=1;i<n;i++) {
           
           if(isP[0][i])
               dp[i] = 0;//abbccbb
           
           else
           {   
               dp[i] = INT_MAX;
               for(int j=0;j<i;j++) {
                 
                 if(isP[j+1][i]&&dp[i]>1+dp[j])
                   dp[i] = 1 + dp[j];
                   
              }
           }
       }
       return dp[n-1];
        
    }
};
// Time Complexity : O(n^2),   Space Complexity : O(n^2)

Another way (Pepcoding solution)

class Solution {
public:
    int minCut(string s) {

        int n = s.size();

        vector<vector<int>> isP(n,vector<int>(n,1));

        for(int gap=0;gap<n;gap++) {
            for(int i=0,j=gap;j<n;i++,j++) {
                if(i>=j) {
                    isP[i][j] = true;
                } else {
                    isP[i][j] = s[i]!=s[j] ? false : isP[i+1][j-1];
                }
            }
        }

        vector<int> dp(n);
        dp[0] = 0;

        for(int i=1;i<n;i++) {

            if(isP[0][i]) {
                dp[i] = 0;
            } else {
                dp[i] = INT_MAX;
                for(int j=i;j>=1;j--) {
                if(isP[j][i]) {
                    dp[i] = min(dp[i],1+dp[j-1]);
                }
             }

            }
            
        }

        return dp[n-1];

        
    }
};