C++ solution using Longest common subsequence


#1

int LCS(string A,string B,int n)
{
int table[n+1][n+1];
for(int i=0;i<n+1;i++)
{
for(int j=0;j<n+1;j++)
{
if(i==0||j==0)
{
table[i][j]=0;
}
else if(A[i-1]==B[j-1])
{
table[i][j]=table[i-1][j-1]+1;
}
else
{
table[i][j]=max(table[i-1][j],table[i][j-1]);
}
}
}
return table[n][n];
}
int Solution::solve(string A) {
int n=A.length();
string B=A;
reverse(B.begin(),B.end());
//cout<<LCS(A,B,n);
int res=LCS(A,B,n);
return res;
}