getting one test case wrong
Lcs with 3 strings
import java.util.*; public class Main { public static void main(String args[]) { Scanner sc = new Scanner(System.in); String s1 = sc.next(); String s2 = sc.next(); String s3 = sc.next(); int n = s1.length(); int m = s2.length(); int k = s3.length(); int dp[][] = new int[n+1][m+1]; char ch[][] = new char[n+1][m+1]; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(s1.charAt(i-1)==s2.charAt(j-1)){ dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1]+1); ch[i][j] = ‘D’; }else{ if(dp[i-1][j]>dp[i][j-1]){ dp[i][j] = Math.max(dp[i][j], dp[i-1][j]); ch[i][j] = ‘U’; }else{ dp[i][j] = Math.max(dp[i][j], dp[i][j-1]); ch[i][j] = ‘L’; } } } } StringBuilder sb = new StringBuilder(); int i=n; int j=m; while(i!=0 && j!=0){ if(ch[i][j]==‘D’){ sb.append(s1.charAt(i-1)); i–; j–; }else if(ch[i][j]==‘L’){ j-=1; }else{ i-=1; } } sb = sb.reverse(); if(s3.length()==0){ System.out.println(“0”); return; } String s4 = sb.toString(); int l = s4.length(); dp = new int[k+1][l+1]; ch = new char[k+1][l+1]; for(int f=1;f<=k;f++){ for(int z=1;z<=l;z++){ if(s3.charAt(f-1)==s4.charAt(z-1)){ dp[f][z] = dp[f-1][z-1]+1; }else dp[f][z] = Math.max(dp[f-1][z], dp[f][z-1]); } } System.out.println(dp[k][l]); } }
@rahulcb72
hello rahul,
pls save ur code on https://ide.codingblocks.com/ and then share the generated link here
are u checking the code?
@rahulcb72
for input
acb
abc
c
your code will output 0 but answer should be 1.
reason -> you are not considering all three strings together .
for first two string two longest common strings can be genrated ie(ab ,ac) now ur code is considering ab only and then taking its lcs with c due to which 0 is coming.
you approach will fail when there will be more than one lcs string possible
yes, you are saying correct
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.