Skip to content

Instantly share code, notes, and snippets.

@thmain
Created May 29, 2023 21:07
Show Gist options
  • Save thmain/531b5feca3246903c8fc6d33aef59749 to your computer and use it in GitHub Desktop.
Save thmain/531b5feca3246903c8fc6d33aef59749 to your computer and use it in GitHub Desktop.
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);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment