Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
984 B
23
Indexable
Never
public class LCS {
    public static int lcs (String s, String t) {
        return lcs (s, t, 0, 0, "");
    }
    
    private static int lcs (String s, String t, int i, int j, String str) {
        if (i == s.length() || j == t.length())
            return str.length();
        if (s.charAt(i) == t.charAt(j))
            str += s.charAt(i);
        return Math.max(lcs(s, t, i+1, j, str), lcs(s, t, i, j+1, str));            
    }
    
    public static void main (String [] args) {
        String a = "abcdefgh";
        String b = "bcwxftjg";
        String c = "xwd";
        String d = "kmns";
        System.out.println("for a and b (should be 4): " + lcs(a,b));
        System.out.println("for b and c (should be 1): " + lcs(b,c));
        System.out.println("for a and d (should be 0): " + lcs(a,d));
        System.out.println("for b and d (should be 0): " + lcs(b,d));
        System.out.println("for c and d (should be 0): " + lcs(c,d));
    }
}
Leave a Comment