DP #09. Minimum Edit Distance. - mbhushan/dynpro GitHub Wiki
(9). Minimum Edit Distance.
Given two strings A & B and operations edit, delete and add, how many minimum
operations would it take to convert string B to string A.
Formula:
if (A[i] == B[j]) {
T[i][j] = T[i-1][j-1]
} else {
T[i][j] = Min (T[i-1][j-1], T[i-1][j], T[i][j-1]) + 1
}
Example Strings:
A = COMMITER
B = COMPUTERS
Min Edit Distance (A, B) = 3
| Indexes |
0 |
C |
O |
M |
P |
U |
T |
E |
R |
S |
| 0 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
| C |
1 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
| O |
2 |
1 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
| M |
3 |
2 |
1 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
| M |
4 |
3 |
2 |
1 |
1 |
2 |
3 |
4 |
5 |
6 |
| I |
5 |
4 |
3 |
2 |
2 |
2 |
3 |
4 |
5 |
6 |
| T |
6 |
5 |
4 |
3 |
3 |
3 |
2 |
3 |
4 |
5 |
| E |
7 |
6 |
5 |
4 |
4 |
4 |
3 |
2 |
3 |
4 |
| R |
8 |
7 |
6 |
5 |
5 |
5 |
4 |
3 |
2 |
3 |
Minimum Edit Distance
- Time complexity is O(m*n)
- Space complexity is O(m*n)