Print Edit Operations
This program prints edit operations to convert one string into another.
Problem Statement
Write a Java program to print edit operations to convert "Eduinq" into "Enquiry".
Source Code
| 1 | public class PrintEditOperations { |
| 2 | public static void main(String[] args) { |
| 3 | System.out.println("Eduinq Print Edit Operations"); |
| 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 | int i=m,j=n; |
| 17 | while(i>0 && j>0){ |
| 18 | if(s1.charAt(i-1)==s2.charAt(j-1)){ i--; j--; } |
| 19 | else if(dp[i][j]==dp[i-1][j-1]+1){ |
| 20 | System.out.println("Replace "+s1.charAt(i-1)+" with "+s2.charAt(j-1)); |
| 21 | i--; j--; |
| 22 | } else if(dp[i][j]==dp[i-1][j]+1){ |
| 23 | System.out.println("Delete "+s1.charAt(i-1)); |
| 24 | i--; |
| 25 | } else { |
| 26 | System.out.println("Insert "+s2.charAt(j-1)); |
| 27 | j--; |
| 28 | } |
| 29 | } |
| 30 | } |
| 31 | } |
Program Output
Eduinq Print Edit Operations Replace d with n Replace u with q Insert r Insert y
Explanation
After the edit distance DP table is built, backtracking from the final cell identifies which operation (replace, delete, or insert) led to each cell's value, printing the sequence of operations needed to transform one string into the other.