Original: http://www.jdepths.com/2012/11/levenshtein-edit-distance-algorithm-in.html

LevenshteinDistance.java

public class LevenshteinDistance
{
 public static void main(String[] args)
 {
  new LevenshteinDistance().solve();
 }
 
 public void solve()
 {
  System.out.println(distance("exponential", "polynomial")); // 6
  System.out.println(distance("jdepths", "pdepths"));   // 1
  System.out.println(distance("snowy", "sunny"));    // 3
 }
 
 public int distance(String s1, String s2)
 {
  int edits[][] = new int[s1.length()+1][s2.length()+1];
  for(int i = 0; i <= s1.length(); i++) edits[i][0] = i;
  for(int j = 1; j <= s2.length(); j++) edits[0][j] = j;
  for(int i = 1; i <= s1.length(); i++) {
   for(int j = 1; j <= s2.length(); j++) {
    int u = (s1.charAt(i-1) == s2.charAt(j-1) ? 0 : 1);
    edits[i][j] = Math.min(
     edits[i-1][j]+1,
     Math.min(edits[i][j-1]+1, edits[i-1][j-1]+u));
   }
  }
  return edits[s1.length()][s2.length()];
 }
}