Skip to content

Instantly share code, notes, and snippets.

@yutarochan

yutarochan/LD.java

Last active August 29, 2015 14:10
Show Gist options
  • Save yutarochan/04181de00d2434b595fd to your computer and use it in GitHub Desktop.
Save yutarochan/04181de00d2434b595fd to your computer and use it in GitHub Desktop.
Download ZIP
Raw
LD.java
public class LD {
public static void main(String[] args) {
// Testing Kitten & Sitting...
String s1 = "kitten";
String s2 = "sitting";
System.out.println(computeLD(s1, s2, s1.length(), s2.length()));
}
public static int computeLD(String s1, String s2, int s1_l, int s2_l) {
int cost = 0;
if (s1_l == 0) return s1_l;
if (s2_l == 0) return s2_l;
if (s1.charAt(s1_l-1) == s2.charAt(s2_l-1)) cost = 0; else cost = 1;
return Math.min(Math.min(computeLD(s1,s2,s1_l-1,s2_l)+1,computeLD(s1,s2,s1_l,s2_l-1)+1),computeLD(s1,s2,s1_l-1,s2_l-1)+cost);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment