This Java program solves the minimum edit distance problem, also known as the Levenshtein distance problem, using dynamic programming. The goal is to compute the minimum number of operations required to convert one string into another, where the allowed operations are insertions, deletions, and substitutions.
Java Program
public class EditDistance {
// Function to calculate the minimum edit distance between two strings
public static int minEditDistance(String str1, String str2) {
int m = str1.length();
int n = str2.length();
// DP table where dp[i][j] represents the minimum edit distance
// between the first i characters of str1 and the first j characters of str2
int[][] dp = new int[m + 1][n + 1];
// Fill the dp table
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0) {
// If first string is empty, we need to insert all characters of second string
dp[i][j] = j;
} else if (j == 0) {
// If second string is empty, we need to delete all characters of first string
dp[i][j] = i;
} else if (str1.charAt(i – 1) == str2.charAt(j – 1)) {
// Characters match, no cost required
dp[i][j] = dp[i – 1][j – 1];
} else {
// Characters do not match, we consider all operations: insert, remove, replace
dp[i][j] = 1 + Math.min(dp[i – 1][j – 1], // Replace
Math.min(dp[i – 1][j], // Remove
dp[i][j – 1])); // Insert
}
}
}
// The last cell dp[m][n] contains the minimum edit distance
return dp[m][n];
}
public static void main(String[] args) {
String str1 = “kitten”;
String str2 = “sitting”;
// Find and print the minimum edit distance between str1 and str2
int result = minEditDistance(str1, str2);
System.out.println(“Minimum edit distance between \”” + str1 + “\” and \”” + str2 + “\” is: ” + result);
}
}
Explanation of the Program Structure
This program calculates the minimum edit distance (also known as Levenshtein distance) between two strings using a dynamic programming approach. The edit distance measures how many operations (insertions, deletions, or substitutions) are needed to convert one string into another.
- minEditDistance function: This function computes the minimum edit distance between two strings,
str1andstr2. It creates a dynamic programming tabledp[i][j]where each entry represents the minimum number of operations required to convert the firsticharacters ofstr1into the firstjcharacters ofstr2. - Dynamic Programming Table (dp): The 2D table
dp[i][j]is filled using a bottom-up approach. If the characters match, no operation is required. If they don’t match, we compute the minimum of the three possible operations (insertion, deletion, substitution), and add 1 to account for the current operation. - Main logic: The program iterates over all characters of both strings. For each pair of characters, it updates the DP table based on whether the characters match or not. The base case is when one of the strings is empty, in which case the edit distance is the length of the other string (i.e., all characters need to be inserted or deleted).
- Base case: When one of the strings is empty, the edit distance is the length of the other string because we would need to insert or delete every character. This is represented by initializing the first row and first column of the DP table.
- main function: This function initializes two sample strings, calls the
minEditDistancefunction, and prints the minimum edit distance between the two strings.
Step-by-Step Process:
- We initialize a dynamic programming table
dpof size(m+1) x (n+1), wheremandnare the lengths of the two input strings. - We iterate through each character of both strings. If characters match, we copy the value from the diagonal cell
dp[i-1][j-1]. If they don’t match, we compute the minimum of three possible operations: insertion, deletion, or substitution. - The base case handles when one of the strings is empty, and the DP table is initialized accordingly with the number of operations equal to the length of the other string.
- The final result, stored in
dp[m][n], represents the minimum edit distance between the two strings.
Example:
Consider the following two strings:
str1 = "kitten"
str2 = "sitting"
The minimum edit distance between “kitten” and “sitting” is 3. The program will output:
Minimum edit distance between "kitten" and "sitting" is: 3
This means we need 3 operations (substitution of ‘k’ to ‘s’, substitution of ‘e’ to ‘i’, and insertion of ‘g’) to convert “kitten” into “sitting”.
Conclusion:
This Java program efficiently solves the minimum edit distance problem using dynamic programming. The time complexity of this solution is O(m * n), where m and n are the lengths of the two input strings. This approach ensures that all possible transformations are considered, resulting in an optimal solution.
