question link-> Palindromic Partitioning | Practice | GeeksforGeeks
Solution->
class Solution{
public:
bool isPalindrome(string str, int i, int j)
{
if(i==j)
{
return true;
}
if(i>j)
{
return false;
}
while(i<j)
{
if(str[i]!=str[j])
{
return false;
}
i++;
j–;
}
return true;
}
int dp[500][500];
int solve(string str, int i, int j)
{
if(i>=j){
return 0;
}
if(isPalindrome(str,i,j)==true)
{
return 0;
}
if(dp[i][j]!=-1)
{
return dp[i][j];
}
int mn=INT_MAX;
for(int k=i;k<=j-1;k++)
{
int left,right;
if(dp[i][k]!=-1)
left = dp[i][k];
else
{
left = solve(str,i,k);
dp[i][k] = left;
}
if(dp[k+1][j]!=-1)
right = dp[k+1][j];
else
{
right = solve(str,k+1,j);
dp[k+1][j] = right;
}
int temp = 1 + left + right;
mn = min(mn,temp);
}
dp[i][j]=mn;
return dp[i][j];
}
int palindromicPartition(string str)
{
// code here
memset(dp,-1,sizeof(dp));
int i=0,j=str.length()-1;
return solve(str,i,j);
}
};
