簡單地說，就是僅通過插入(insert)、刪除(delete)和替換(substitute)個操作將一個字符串s1變換到另一個字符串s2的最少步驟數。熟悉算法的同學很容易知道這是個動態規劃問題。
其實一個替換操作可以相當於一個delete+一個insert，所以我們將權值定義如下：
I (insert)：1
D (delete)：1
S (substitute)：1
示例：
intention->execution
Minimal edit distance：
delete i ; n->e ; t->x ; insert c ; n->u 求和得cost=5
如上圖所示，d（deletion）代表刪除操作，s（substitution）代表替換操作，i（insertion）代表插入操作。
（為了簡單起見，後面的Edit Distance 簡寫為ED）
如果每種操作的cost（成本）為1，那麼ED = 5.
<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+yOe5+8Tcz+u1vcrHtq/MrLnmu67Oyszivs2yu8TRveK+9sHLoaM8L3A+CjxwPjxwcmUgY2xhc3M9"brush:java;">class Solution {
public:
int minDistance(string word1, string word2) {
const size_t n = word1.size();
const size_t m = word2.size();
int f[n + 1][m + 1];
for(size_t i = 0; i <= n; i++)
f[i][0] = i;
for(size_t j = 0; j <= m; j++)
f[0][j] = j;
for(size_t i = 1; i <= n; i++)
{
for(size_t j = 1; j <= m; j++)
{
if(word1[i - 1] == word2[j - 1])
f[i][j] = f[i - 1][j - 1];
else
{
int mn = min(f[i - 1][j], f[i][j - 1]);
f[i][j] = min(f[i - 1][j - 1], mn) + 1;
}
}
}
return f[n][m];
}
};
同樣，對於動態規劃問題，我們不想使用O(m*n)的空間復雜度。
可以通過滾動數組的形式，將空間復雜度降至O(min(m, n))
參考網址：編輯距離-自然語言處理 編輯距離-張大神
