Problem
Task
-
Given two strings , how many minimum edits(Update,Delete or insert) are
required to convert one string to another.
Time
Complexity is O(m*n)
Space
Complexity is O(m*n)
Self- Understanding snippet
public class MinimumEditDistance {
public static void main(String[] args) {
String str1 = "azced";
String str2 = "abcdef";
MinimumEditDistance editDistance = new MinimumEditDistance();
int result = editDistance.dynamicEditDistance(str1.toCharArray(),str2.toCharArray());
System.out.print(result);
}
int dynamicEditDistance(char[] str1, char[] str2) {
int temp[][] = new int[str1.length + 1][str2.length + 1];
//Distance b/w null string and str1
for (int i = 0; i < str1.length; i++)
temp[i][0] = i;
//Distance b/w null string and str2
for (int i = 0; i < str2.length; i++)
temp[0][i] = i;
//Insertion-> Top, Deletion-> Left,Replace->Diagonol
for (int i = 1; i <= str1.length; i++) {
for (int j = 1; j <= str2.length; j++) {
if (str1[i - 1] == str2[j - 1])
temp[i][j] = temp[i - 1][j - 1];
else
temp[i][j] = min(temp[i - 1][j], temp[i - 1][j - 1],temp[i][j - 1]) + 1;
}
}
printActualEdits(temp,str1,str2);
return temp[str1.length][str2.length];
}
// Printing what actually edits happened among I,D & R
void printActualEdits(int temp[][],char str1[],char str2[]){
int i=temp.length-1;
int j=temp[0].length-1;
int count=0;
while(true){
if(i==0||j==0)
break;
else if(str1[i-1]==str2[j-1])
{
i--;j--;
}
else if(temp[i][j]==temp[i-1][j-1]+1)
{
count++;
System.out.println("Operation"+ count+" Replace "+str2[j-1]+" With "+str1[i-1]);
i--;j--;
}
else if(temp[i][j]==temp[i][j-1]+1)
{
count++;
System.out.println("Operation"+ count+" Delete "+str2[j-1]);
j--;
}
else if(temp[i][j]==temp[i-1][j]+1)
{
count++;
System.out.println("Operation"+ count+" Insert "+str2[j-1]+" With "+str1[i-1]);
i--;
}
else{
throw new IllegalArgumentException();
}
}
}
int min(int a, int b, int c) {
int min1 = Math.min(a, b);
int min2 = Math.min(min1, c);
return min2;
}
}
Output:
Operation1 Replace f With d
Operation2 Delete d
Operation3 Replace b With z
3
References :
No comments:
Post a Comment