Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
import java.util.*;
public class LongestCommonSubsequenceDPTopDown {
static HashMap<String, Integer> hm = new HashMap<>();
public static int LCS(String A, String B) {
if (A.length() == 0 || B.length() == 0) {
return 0;
}
if(hm.containsKey(A+B)){
return hm.get(A+B);
}
int lenA = A.length();
int lenB = B.length();
// check if last characters are same
if (A.charAt(lenA - 1) == B.charAt(lenB - 1)) {
// Add 1 to the result and remove the last character from both
// the strings and make recursive call to the modified strings.
int x = LCS(A.substring(0, lenA - 1), B.substring(0, lenB - 1));
hm.put(A.substring(0, lenA - 1)+ B.substring(0, lenB - 1), x);
return 1 + x;
} else {
// Remove the last character of String 1 and make a recursive
// call and remove the last character from String 2 and make a
// recursive and then return the max from returns of both recursive
// calls
int y = LCS(A.substring(0, lenA - 1), B.substring(0, lenB));
int z = LCS(A.substring(0, lenA), B.substring(0, lenB - 1));
hm.put(A.substring(0, lenA - 1)+ B.substring(0, lenB), y);
hm.put(A.substring(0, lenA)+ B.substring(0, lenB-1), z);
return Math.max(y, z);
}
}
public static void main(String[] args) {
String A = "ACBDEABCSBEDACBDEABCSBEDACBDEABCSBEDACBDEABCSBED";
String B = "ABCDASBDABCDASBDABCDASBDABCDASBD";
System.out.println("LCS :" + LCS(A, B));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.