Source code in the java programming language

public class Levenshtein {

    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()];
    }

    public static void main(String [] args) {
        String [] data = { "kitten", "sitting", "saturday", "sunday", "rosettacode", "raisethysword" };
        for (int i = 0; i < data.length; i += 2)
            System.out.println("distance(" + data[i] + ", " + data[i+1] + ") = " + distance(data[i], data[i+1]));
    }
}


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


import static java.lang.Math.abs;
import static java.lang.Math.max;

public class Levenshtein {

	public static int ld(String a, String b) { 
		return distance(a, b, -1);
	}
	public static boolean ld(String a, String b, int max) {
		return distance(a, b, max) <= max;
	}
	
	private static int distance(String a, String b, int max) {
		if (a == b) return 0;
		int la = a.length();
		int lb = b.length();
		if (max >= 0 && abs(la - lb) > max) return max+1;
		if (la == 0) return lb;
		if (lb == 0) return la;
		if (la < lb) {
			int tl = la; la = lb; lb = tl;
			String ts = a;  a = b; b = ts;
		}
		
		int[] cost = new int[lb+1];
		for (int i=0; i<=lb; i+=1) {
			cost[i] = i;
		}

		for (int i=1; i<=la; i+=1) {
			cost[0] = i;
			int prv = i-1;
			int min = prv;
			for (int j=1; j<=lb; j+=1) {
				int act = prv + (a.charAt(i-1) == b.charAt(j-1) ? 0 : 1);
				cost[j] = min(1+(prv=cost[j]), 1+cost[j-1], act);
				if (prv < min) min = prv;
			}
			if (max >= 0 && min > max) return max+1;
		}
		if (max >= 0 && cost[lb] > max) return max+1;
		return cost[lb];	
	}
	
	private static int min(int ... a) {
		int min = Integer.MAX_VALUE;
		for (int i: a) if (i<min) min = i;
		return min;
	}
	
	public static void main(String[] args) {
		System.out.println(
			ld("kitten","kitten") + " " + // 0
			ld("kitten","sitten") + " " + // 1
			ld("kitten","sittes") + " " + // 2
			ld("kitten","sityteng") + " " + // 3
			ld("kitten","sittYing") + " " + // 4
			ld("rosettacode","raisethysword") + " " + // 8 
			ld("kitten","kittenaaaaaaaaaaaaaaaaa") + " " + // 17
			ld("kittenaaaaaaaaaaaaaaaaa","kitten") // 17
		);
		System.out.println(
			ld("kitten","kitten", 3) + " " + // true
			ld("kitten","sitten", 3) + " " + // true
			ld("kitten","sittes", 3) + " " + // true
			ld("kitten","sityteng", 3) + " " + // true
			ld("kitten","sittYing", 3) + " " + // false
			ld("rosettacode","raisethysword", 3) + " " + // false 
			ld("kitten","kittenaaaaaaaaaaaaaaaaa", 3) + " " + // false
			ld("kittenaaaaaaaaaaaaaaaaa","kitten", 3) // false
		);
	}
}