code: public class Levenshtein{
      public static int levenshtein(String s, String t){
          /* if either string is empty, difference is inserting all chars
           * from the other
           */
          if(s.length() == 0) return t.length();
          if(t.length() == 0) return s.length();
  
          /* if first letters are the same, the difference is whatever is
           * required to edit the rest of the strings
           */
          if(s.charAt(0) == t.charAt(0))
              return levenshtein(s.substring(1), t.substring(1));
  
          /* else try:
           *      changing first letter of s to that of t,
           *      remove first letter of s, or
           *      remove first letter of t
           */
          int a = levenshtein(s.substring(1), t.substring(1));
          int b = levenshtein(s, t.substring(1));
          int c = levenshtein(s.substring(1), t);
  
          if(a > b) a = b;
          if(a > c) a = c;
  
          //any of which is 1 edit plus editing the rest of the strings
          return a + 1;
      }
  
      public static void main(String[] args) {
          String s1 = "kitten";
          String s2 = "sitting";
          System.out.println("distance between '" + s1 + "' and '"
                  + s2 + "': " + levenshtein(s1, s2));
          s1 = "rosettacode";
          s2 = "raisethysword";
          System.out.println("distance between '" + s1 + "' and '"
                  + s2 + "': " + levenshtein(s1, s2));
          StringBuilder sb1 = new StringBuilder(s1);
          StringBuilder sb2 = new StringBuilder(s2);
          System.out.println("distance between '" + sb1.reverse() + "' and '"
                  + sb2.reverse() + "': "
                  + levenshtein(sb1.reverse().toString(), sb2.reverse().toString()));
      }
  }
  