Posts

Palindrome Partitioning GFG Solution

int dp[501][501];
    bool isPalindrome(string str,int i,int j)
    {
        while(i<=j)
        {
            if(str[i]!=str[j])
            return false;
            i++;
            j--;
        }
        return 1;
    }
    int solve(string str,int i,int j)
    {
        if(i>=j)
        return 0;
        
        if(dp[i][j]!=-1)
        return dp[i][j];
        
        if(isPalindrome(str,i,j))
        return 0;
        
        int mn=INT_MAX;
        
        for(int k=i;k<j;k++)
        {
            int left,right;
            
            if(dp[i][k]!=-1)
            left=dp[i][k];
            else
            left=solve(str,i,k);
            
            if(dp[k+1][j]!=-1)
            right=dp[k+1][j];
            else
            right=solve(str,k+1,j);
            
            int temp=left+right+1;
            mn=min(mn,temp);
        }
        return dp[i][j]=mn;
    }
    int palindromicPartition(string str)
    {
        // code here
        int i=0,j=str.size()-1;
        memset(dp,-1,sizeof(dp));
        return solve(str,i,j);
    }

Post a Comment

Please do not enter any spam link in the comment box.