Levenshtein distance

Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (i.e. insertions, deletions or substitutions) required to change one word into the other.

Iterate Version:
http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Java

public class LevenshteinDistance {                                               
    private static int minimum(int a, int b, int c) {                            
        return Math.min(Math.min(a, b), c);                                      
    }                                                                            
 
    public static int computeLevenshteinDistance(String str1,String str2) {      
        int[][] distance = new int[str1.length() + 1][str2.length() + 1];        
 
        for (int i = 0; i <= str1.length(); i++)                                 
            distance[i][0] = i;                                                  
        for (int j = 1; j <= str2.length(); j++)                                 
            distance[0][j] = j;                                                  
 
        for (int i = 1; i <= str1.length(); i++)                                 
            for (int j = 1; j <= str2.length(); j++)                             
                distance[i][j] = minimum(                                        
                        distance[i - 1][j] + 1,                                  
                        distance[i][j - 1] + 1,                                  
                        distance[i - 1][j - 1] + ((str1.charAt(i - 1) == str2.charAt(j - 1)) ? 0 : 1));
 
        return distance[str1.length()][str2.length()];                           
    }                                                                            
}
Not recursive and faster 

public int LevenshteinDistance (String s0, String s1) {                          
    int len0 = s0.length() + 1;                                                  
    int len1 = s1.length() + 1;                                                 
    // the array of distances         
    int[] cost = new int[len0];      
    int[] newcost = new int[len0];        
    // initial cost of skipping prefix in String s0            
    for (int i = 0; i < len0; i++) cost[i] = i;       
    // dynamicaly computing the array of distances     
    // transformation cost for each letter in s1      
    for (int j = 1; j < len1; j++) {   
        // initial cost of skipping prefix in String s1   
        newcost[0] = j;       
        // transformation cost for each letter in s0    
        for(int i = 1; i < len0; i++) {     
            // matching current letters in both strings    
            int match = (s0.charAt(i - 1) == s1.charAt(j - 1)) ? 0 : 1;     
            // computing cost for each transformation   
            int cost_replace = cost[i - 1] + match; 
            int cost_insert  = cost[i] + 1;     
            int cost_delete  = newcost[i - 1] + 1;    
            // keep minimum cost                                                    
            newcost[i] = Math.min(Math.min(cost_insert, cost_delete), cost_replace);
        }
        // swap cost/newcost arrays      
        int[] swap = cost; cost = newcost; newcost = swap;   
    }                          
    // the distance is the cost for transforming all letters in both strings    
    return cost[len0 - 1];     
}

http://rosettacode.org/wiki/Levenshtein_distance#Java

    public static int distance(String a, String b) {
        a = a.toLowerCase();
        b = b.toLowerCase();
        // i == 0
        int [] costs = new int [b.length() + 1];
        for (int j = 0; j < costs.length; j++)
            costs[j] = j;
        for (int i = 1; i <= a.length(); i++) {
            // j == 0; nw = lev(i - 1, j)
            costs[0] = i;
            int nw = i - 1;
            for (int j = 1; j <= b.length(); j++) {
                int cj = Math.min(1 + Math.min(costs[j], costs[j - 1]), a.charAt(i - 1) == b.charAt(j - 1) ? nw : nw + 1);
                nw = costs[j];
                costs[j] = cj;
            }
        }
        return costs[b.length()];
    }

Recursion Version:
http://rosettacode.org/wiki/Levenshtein_distance#Java

    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;
    }

EPI Java Solution

LevenshteinDistance.java