Calculate Edit Distance
This program calculates edit distance between two strings.
Problem Statement
Write a Java program to calculate edit distance between "Eduinq" and "Enquiry".
Source Code
| 1 | public class EditDistance { |
| 2 | public static void main(String[] args) { |
| 3 | System.out.println("Eduinq Edit Distance"); |
| 4 | String s1="Eduinq", s2="Enquiry"; |
| 5 | int m=s1.length(), n=s2.length(); |
| 6 | int[][] dp=new int[m+1][n+1]; |
| 7 | for(int i=0;i<=m;i++){ |
| 8 | for(int j=0;j<=n;j++){ |
| 9 | if(i==0) dp[i][j]=j; |
| 10 | else if(j==0) dp[i][j]=i; |
| 11 | else if(s1.charAt(i-1)==s2.charAt(j-1)) |
| 12 | dp[i][j]=dp[i-1][j-1]; |
| 13 | else dp[i][j]=1+Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1])); |
| 14 | } |
| 15 | } |
| 16 | System.out.println("Edit distance = "+dp[m][n]); |
| 17 | } |
| 18 | } |
Program Output
Eduinq Edit Distance Edit distance = 4
Explanation
The DP table stores the minimum number of insert, delete, or replace operations needed to convert one prefix of s1 into a prefix of s2, and the final cell gives the minimum total edit distance between the full strings.