Dene the edit distance between two strings x and y, as the smallest number of si
ID: 3580445 • Letter: D
Question
Dene the edit distance between two strings x and y, as the smallest number of single character edits to x which would turn it into y. The allowed edits are: delete a character, insert a character from y, replace a character into a character in y.
Example:
x: ANGEL
y = DANGER
The optimal steps to turn x into y are:
1. insert D from x
2. match A from x and y
3. match N from x and y
4. match G from x and y
5. match E form x and y
6. replace L with R from x
Total # of edits is 2 (steps 1 and 6)
A much less optimal sequence of steps (with a larger number of edits would be)
1. replace A with D
2. insert A
3. match N from x and y
4. match G from x and y
5. match E form x and y
6. insert R
This has 3 edits (steps 1,2 and 6)
Write a dynamic programming solution to this problem. To do so, remember rst to nd how the solution to the full problem, which is the smallest number of edits converting x into y, can be dened using solutions to the same problem dened for smaller portions of x or y or both. Once you’ve done that, you simply compute the solutions to the smallest subproblems, then use these to compute the solutions to the larger subproblem
Explanation / Answer
#include<iostream.h>
int editDist(char x, int m, char y, int n)
{
int c[m][n], i, j;
// initialize
for (i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if (i == 0)
{
// source string is NULL, so 'j' insert operations needed
c[i][j] = j*1;
}
else if (j == 0)
{
// target string is NULL, so 'i' delete operations needed
c[i][j] = i*1;
}
else
{
c[i][j] = -1;
}
} //end of for loop j
} // end of for loop i
for(i=1;i<m;i++) {
for(j=1;j<n;j++) {
int p = c[i-1][j] + 1; // for insertion
int q = c[i][j-1] + 1; // for deletion
int r = c[i-1][j-1] + (str1[i-1] != str2[j-1])*1; // for replacement
c[i][j] = min(p, min(q,r));
}
}
return c[m-1][n-1];
}
int min(int a,int b)
{
If (a<b)
return a;
else
return b;
}
//main
void main()
{
char x,y;
int m,n;
cout<<”Enter string 1: “;
cin>>x;
cout<<”Enter string 2: “;
cin>>y;
m=strlen(x);
n=strlen(y);
res = editDist(x, m+1, y, n+1);
cout<<" Minimum edits required : "<<res;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.