How many single-letter changes turn one word into another? Spell checkers ask this all the time.
What to build
A dynamic program that finds the edit distance between two words.
Requirements
- One edit inserts a letter, deletes a letter, or replaces a letter with another.
- Fill a table indexed by the lengths of the two prefixes.
- Print the fewest edits needed.
Input
Two lines, each with a word.
Output
The edit distance.
Constraints
Each word has 1 to 100 letters.
Example
Input:
kitten
sitting
Output:
3
Why it works
Look at the last letters. They either match, or the final edit was an insert, a delete or a replace, and each of those leaves a smaller pair of prefixes that is already solved.
Examples
kitten sitting
3
horse ros
3
Hints
Hint 1
Let `d[i][j]` be the fewest edits that turn the first `i` letters of one word into the first `j` letters of the other.
Hint 2
Row 0 and column 0 are the cost of inserting or deleting everything: `d[0][j] = j` and `d[i][0] = i`.
Hint 3
If the last letters match, no edit is needed. Otherwise it is 1 plus the smallest of the three neighbouring cells.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#include <string.h>
int d[101][101];
int min3(int x, int y, int z) {
int m = x < y ? x : y;
return m < z ? m : z;
}
int main(void) {
char a[101], b[101];
scanf("%100s %100s", a, b);
int n = strlen(a), m = strlen(b);
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (i == 0) d[i][j] = j;
else if (j == 0) d[i][j] = i;
else if (a[i - 1] == b[j - 1]) d[i][j] = d[i - 1][j - 1];
else d[i][j] = 1 + min3(d[i - 1][j], d[i][j - 1], d[i - 1][j - 1]);
}
}
printf("%d\n", d[n][m]);
return 0;
}