Simple iterative solution without using dp


#1

int Solution::minCut(string A) {

int i,j,k,n,row,col,inc,ite;
n=A.size();
//int dp[n][n]={0};
ite=k=0;
string str,temp;
// for(i=0,j=0;i<n;i++,j++)
// {
//     dp[i][j]=
// }
if(n==1)
{
    return 0;
}

// for(i=0,j=1;j<n;j++)
// {
//     // row=i;
//     // col=j;
//     for(row=i,col=j;row<n && col<n;row++,col++)
//     {
//         if(A[i]==A[j])
//         {
//             dp[i][j]=dp[i-1][j-1];
//         }
//         else
//         {
//             dp[i][j]=1+min(dp[i+1][j],dp[i][j-1]);
//         }
//     }
// }
for(j=0;j<n;j=j+inc)
{
    str.clear(); 
   
for(i=j;i<n;i++)
{
    str=str+A[i];
    temp=str;
    reverse(temp.begin(),temp.end());
    if(temp==str)
    {
        inc=str.length();
    }
}
k++;
}

for(j=n-1;j>=0;j=j-inc)
{
    str.clear(); 
   
for(i=j;i>=0;i--)
{
    str=str+A[i];
    temp=str;
    reverse(temp.begin(),temp.end());
    if(temp==str)
    {
        inc=str.length();
    }
}
ite++;
}

return min(k-1,ite-1);

}