(每日算法)Leetcode--Edit Distance(编辑距离) - c++编程基础

简单地说，就是仅通过插入(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

Edit Distance用于衡量两个strings之间的相似性。两个strings之间的 Minimum edit distance是指把其中一个string通过编辑（包括插入，删除，替换操作）转换为另一个string的最小操作数。

如上图所示，d（deletion）代表删除操作，s（substitution）代表替换操作，i（insertion）代表插入操作。（为了简单起见，后面的Edit Distance 简写为ED）如果每种操作的cost（成本）为1，那么ED = 5.

我们定义D（i，j）为 X 的前i个字符 X[1...i] 与 Y 的前j个字符 Y[1...j] 之间的距离，其中0

<??http://www.2cto.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))

参考网址：编辑距离-自然语言处理编辑距离-张大神