LevenshteinDistance.java

package dynamicprogramming;

public class LevenshteinDistance {

    /*
     * Compute Levenshtein distance between two strings.
     * Given two strings, compute the Levenshtein distance between them i.e.
     * the minimum number of edits required to convert one string into the other.
     *
     * For example, the Levenshtein distance between "kitten" and "sitting" is 3.
     * The minimum steps required to transform the former into latter are:
     *      kitten → sitten (substitution of "s" for "k")
     *      sitten → sittin (substitution of "i" for "e")
     *      sittin → sitting (insertion of "g" at the end)
     *
     * Runtime Complexity:
     * Quadratic, O(n2)
     *
     * Memory Complexity:
     * Quadratic, O(n2)
     *
     * Levenshtein distance 'LD' is  a measure of the difference between two strings s1 and s2.
     * It is the minimum number of deletions, insertions, or substitutions required to transform s1 into s2.
     *
     * if s1 is empty, return length of s2
     * if s2 is empty, return length of s1
     * if last characters of s1 and s2 match, initialize 'cost' to 0, otherwise initialize 'cost' to 1
     *      recursively compute 'd1' [(Levenshtein distance of s1 - 1 and s2) + 1 ]
     *      recursively compute 'd2' [(Levenshtein distance of s1 and s2 - 1) + 1]
     *      recursively compute 'd3' [(Levenshtein distance of s1 - 1 and s2 - 1) + cost]
     *      return minimum of d1, d2, d3
     * */

    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) {

        if (str1 == str2) return 0;

        if (str1.length() == 0)
            return str2.length();

        if (str2.length() == 0)
            return str1.length();


        int[][] d = new int[str1.length() + 1][str2.length() + 1];

        for (int i = 0; i <= str1.length(); i++) {
            d[i][0] = i;
        }

        for (int j = 1; j <= str2.length(); j++) {
            d[0][j] = j;
        }

        int cost;
        for (int i = 1; i <= str1.length(); i++) {
            for (int j = 1; j <= str2.length(); j++) {

                if (str1.charAt(i - 1) == str2.charAt(j - 1))
                    cost = 0;
                else
                    cost = 1;

                d[i][j] = minimum(
                        d[i - 1][j] + 1,
                        d[i][j - 1] + 1,
                        d[i - 1][j - 1] + cost);
            }
        }

        return d[str1.length()][str2.length()];
    }



    public static void main(String[] args) {

        System.out.println(computeLevenshteinDistance("", ""));
        System.out.println(computeLevenshteinDistance("kite", ""));
        System.out.println(computeLevenshteinDistance("", "kitten"));
        System.out.println(computeLevenshteinDistance("computer", "computer"));
        System.out.println(computeLevenshteinDistance("test", "text"));
        System.out.println(computeLevenshteinDistance("kitten", "sitting"));
        System.out.println(computeLevenshteinDistance("this is a string", "This is a string"));
        System.out.println(computeLevenshteinDistance("this is a string", "thisisastring"));
        System.out.println(computeLevenshteinDistance("appropriate meaning", "approximate matching"));
        System.out.println(computeLevenshteinDistance("intention", "execution"));
        System.out.println(computeLevenshteinDistance("min", "max"));
    }
}