Question

develop a recursive function to compute LCS (x,y)

Answer 1

public static String lcs(String X, String Y)
{
    int a = X.length();
    int b = Y.length();
    if(a == 0 || b == 0){
        return "";
 }else if(X.charAt(a-1) == Y.charAt(b-1)){
        return lcs(X.substring(0,a-1),Y.substring(0,b-1))
            + X.charAt(a-1);
    }else{
        String x = lcs(X, Y.substring(0,b-1));
        String y = lcs(X.substring(0,a-1), b);
        return (x.length() > y.length()) ? x : y;
    }
}

Explanation:LCS is longest common subsequence between the two strings.For eg in "XYZ" and "YZS" lcs is YZ

In this program firstly we stored the length of strings in a and b respectively.After that if size of string is 0 then obviously we print nothing thenwe checked if character at a-1 length of X is equal to character at b-1 lengthof Y then we call LCS function with substring 0 to a-1 and o to b-1 respectively otherwise we take two more strings x and y and store the LCS call with X,Y.substring(0,b-1) and X.substring(0,a-1),b and that is all.Thankyou