LongestCommonSubsequenceDPTopDown.java

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));
      }
}