首页 > 代码库 > 字符串编辑距离
字符串编辑距离
有两个字符串A和B，对A可以进行如下的操作：插入一个字符，删除一个字符，替换一个字符。问A可以通过最少多少次操作变为B？我们定义这个结果为字符串的最小编辑距离。
DP问题。记f(x,y)为字符串A前x个字符与字符串B前y个字符之间的编辑距离，那么：
f(x,y) = f(x-1,y-1) if(A[x]==B[y])
= min{f(x-1,y-1), f(x-1,y), f(x,y-1)}+1 if(A[x]!=B[y])
答案为f[A.length][B.length]。时间复杂度O(n^2)。
代码如下：
1 int editDistance(char* A, char* B, int lenA, int lenB)
2 { 3 if (!A || !B || lenA < 0 || lenB < 0) 4 return -1; 5 int ed[lenA+1][lenB+1]; 6 for (int i = 0; i <= lenA; i++) 7 ed[i][0] = i; 8 for (int i = 0; i <= lenB; i++) 9 ed[0][i] = i;10 for (int i = 1; i <= lenA; i++)11 {12 for (int j = 1; j <= lenB; j++)13 {14 if （A[i] == B[j])15 ed[i][j] = ed[i-1][j-1];16 else17 ed[i][j] = min(ed[i-1][j-1], ed[i-1][j], ed[i][j-1]) + 1;18 }19 }20 return ed[lenA][lenB];21 }
另外，有一种递归的写法，这里不再写出；上面的非递归方式更加清晰。
字符串编辑距离
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。