Please check my code

#1

can u check my code and figure out the error?

#2

The logic doesn’t seem to be correct to me, you cannot judge just on the basis of the length of LCS,
Consider three strings
s1: aaabbb, s2:bbbccc, s3: cccaaa
As per your code answer will be:

= min(LCA(s1,s2),LCA(s2,s3),LCA(s3,s1))
= min(3,3,3)
= 3

However, if you think logically there is no common subsequence in all three.
Now the approach of solving this problem will be
Take all the three strings together and find the LCS of all three together

for(int i=0;i<=a.size();i++)
    {
        for(int j=0;j<=b.size();j++)
        {
            for(int k=0;k<=c.size();k++)
            {
                if(i==0 || j==0 || k==0)
                    dp[i][j][k]=0;
                else if(a[i-1]==b[j-1] && a[i-1]==c[k-1])
                    dp[i][j][k]=1+dp[i-1][j-1][k-1];
                else
                    dp[i][j][k]=max({dp[i][j][k-1],dp[i-1][j][k],dp[i][j-1][k]});
            }
        }
    }

The answer will be stored in dp[a.size()][b.size()][c.size()]

#3

https://ide.codingblocks.com/s/340263 please have a look at this

1 Like