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.

Quick Links to Explore