1. Introduction

The Levenshtein distance, also known as the Edit distance, is a measure of the similarity between two strings. The distance is the number of deletions, insertions, or substitutions required to transform one string into the other. It’s a useful metric in various applications, including spell checkers, DNA sequence analysis, and natural language processing.

2. Program Steps

1. Create a 2D array of dimensions (m+1) x (n+1), where m and n are the lengths of the two input strings. This array will store the edit distances for substrings of the two input strings.

2. Initialize the first row and first column with values 0 to m and 0 to n respectively. These represent the costs of turning a substring into an empty string.

3. Loop through the array, filling in each cell with the minimum of:

– The value above plus one

– The value to the left plus one

– The value diagonally above and to the left plus one (if the current characters of the strings being compared are different) or just the diagonal value (if they are the same).

4. The value at the bottom-right of the array is the Levenshtein distance for the two strings.

3. Code Program

public class LevenshteinDistance {

    public static int calculate(String a, String b) {
        int m = a.length();
        int n = b.length();
        int[][] dp = new int[m + 1][n + 1];

        // Initializing the first column
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }

        // Initializing the first row
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }

        // Filling in the array using a bottom-up dynamic programming approach
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                }
            }
        }

        return dp[m][n];
    }

    public static void main(String[] args) {
        String a = "kitten";
        String b = "sitting";
        System.out.println("Edit distance between " + a + " and " + b + " is: " + calculate(a, b));
    }
}

Output:

Edit distance between kitten and sitting is: 3

4. Step By Step Explanation

1. The 2D array dp is initialized such that dp[i][j] represents the Levenshtein distance between the first i characters of string a and the first j characters of string b.

2. The first row and column represent transformations involving the empty string. Hence, dp[i][0] is i and dp[0][j] is j.

3. For each subsequent character pair, if the characters are the same, the current distance value is the same as that for the previous characters. Otherwise, it's the smallest of the values from the top, left, or top-left, plus one.

4. The final value, dp[m][n], is the edit distance between the two input strings.