Edit Distance

Problem

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

---

Idea

设状态为 f[i][j],表示 A[0,i] 和 B[0,j] 之间的最小编辑距离。设 A[0,i] 的形式是 str1c,B[0,j] 的形式是 str2d,

• 如果 c==d,则 f[i][j]=f[i-1][j-1];
• 如果 c!=d,
• 如果将 c 替换成 d,则 f[i][j]=f[i-1][j-1]+1;
• 如果在 c 后面添加一个 d,则 f[i][j]=f[i][j-1]+1; // 这里为什么是f[i][j-1]，因为f[i][j]表示的是a[0,i],b[0,i]之间最小距离，若选择添加一个d,那么这个操作的上一步的数组应该是a[0,i],b[0,i-1]，a是不能动的，因为a[i]还没匹配呢.
• 如果将 c 删除,则 f[i][j]=f[i-1][j]+1; 若删除c，则是b[j]不动，因为还没匹配.

---

Solution

---