longestCommonString.java

import java.util.HashMap;

public class longestCommonString {

    public static int find(String s1, String s2, HashMap<String, Integer> map){
        if (s1 == null || s1.length() ==0)
            return 0;

        if (s2 == null || s2.length() ==0)
            return 0;

        if(map.containsKey(s1+","+s2))
            return map.get(s1+","+s2);

        if (s1.charAt(0) == s2.charAt(0)){
            int x = find(s1.substring(1), s2.substring(1), map);
            map.put(s1.substring(1)+","+s2.substring(1), x);
            return 1 + x;
        }else{
            int x = find(s1, s2.substring(1), map);
            map.put(s1+","+s2.substring(1), x);
            return x;
        }
    }

    public static void main(String[] args) {
        long start =System.currentTimeMillis();
        String A = "tutorialhorizon";
        String B = "dynamictutorialProgramming";
//        String A = "BCDEC";
//        String B = "BCXC";
        HashMap<String, Integer> map = new HashMap<>();
        System.out.println("LCS length : " + find(A, B, map));
        long end =System.currentTimeMillis();
        System.out.println(end-start);
    }
}