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 q with y Replace n with r Replace d with q Insert n
Explanation
Backtracking reconstructs operations. - Replace, insert, delete printed. - Together shows transformation steps. Conclusion: Shows how to print edit operations using DP.