dato datuashvili dato datuashvili - 7 months ago 26
Java Question

Java: Longest common subsequence

I have following code:

public class LCS1 {

public static String lcs(String a, String b) {
String x;
String y;

int alen = a.length();
int blen = b.length();
if (alen == 0 || blen == 0) {
return "";
} else if (a.charAt(alen - 1) == b.charAt(blen - 1)) {
return lcs(a.substring(0, alen - 1), b.substring(0, blen - 1));
} else {
x = lcs(a, b.substring(0, blen - 1));
y = lcs(a.substring(0, alen - 1), b);
}
return (x.length() > y.length()) ? x : y;
}

public static void main(String[] args) {
String a = "computer";
String b = "houseboat";
System.out.println(lcs(a, b));
}
}


It should return "
out
" but an empty string returns what is problem?

Answer

I'm not sure, but I think, the lines

else if (a.charAt(alen-1)==b.charAt(blen-1)){
  return lcs(a.substring(0,alen-1),b.substring(0,blen-1));
}

should be changed to

else if (a.charAt(alen-1)==b.charAt(blen-1)){
  return lcs(a.substring(0,alen-1),b.substring(0,blen-1)) + a.charAt(alen-1);
}

Otherwise no concatenation of strings takes place and only "" is returned.