设计一个算法，计算两个字符串之间的编辑距离

-1

两个字符串s和t的编辑距离是单字符操作（插入，删除，替换）需要的最小数目将s转换为t。假设m和n是字符串s和t的长度。

设计一个O(nm)时间和O(nm)空间算法来计算s和t之间的编辑距离。

我的想法：

是不是很容易，只需比较两个字符串每次一个字符：

L = maximum(length(s), length(t)) 
for i in L: 
    if i > length(s): 
     distance += length(t) - i 
     break 
    if i > length(t): 
     distance += length(s) - i 
     break 
    if s[i] != t[i]: 
     distance += 1

如果我错了，那么我应该使用编辑距离算法表？是的，我该如何设计一个O(nm)时间和O(nm)空间算法？

来源

2015-06-23 James the Great

[Levenshtein距离]（https://en.wikipedia.org/wiki/Levenshtein_distance） – amit

另请参阅[本教程]（http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Edit/）。 –

如果s ='ABCDEF'和t ='BCDEFG'（编辑距离= 2），那么显然你的算法会失败。 –

谢谢@Roberto ATTIAS他的回答，但下面是完整的算法我要找：

L1 = length(string1) 
L2 = length(string2) 
for i in L1: 
    table[i][0] = i 
for i in L2: 
    table[0][i] = i 
for i in L1: 
    for j in L2: 
     m = minimum(table[i-1][j],table[i][j-1])+1 
     if s[i] == t[j]: subvalue = 1 
     else: subvalue = 0 
     table[i][j] = minimum(m, table[i-1][j-1] + subvalue) 
return table[L1][L2]

上述算法如下编辑距离算法表中的战略

来源

2015-06-24 22:45:05

考虑字符串abcd和bcd。他们不同的一个删除，但你的方法将他们计为距离4.

你想要做的是找到最长的公共子序列。这是一个众所周知的问题，你可以通过谷歌了解很多代码示例，其中一个解决方案实际上是O（NM）。

例如，对于字符串abcdqef和xybcdzzzef，LCS是bcdqef。考虑序列中两个字符串：

a-bcd-q-ef 
xy-bcd-zzz-ef

可以转化成a与xy一个修改和一个插入，并q为zzz一个修改和两个插入。如果仔细考虑，所需操作数（即距离）是不属于LCS的最长字符串中的字符数。

来源

2015-06-23 08:09:58

您在示例中错过了“q”字符串“abcdef” –

O（NM）是什么意思？如果字符串是“狗”和“猫”，是否O（3 x 4）= O（12）这意味着算法应该小于12步？ –

修正的例子。 O（NM）意味着在你的问题中同样的事情，它表明算法的时间/空间复杂性。 “谈论”步骤“并不完全正确，你可能想阅读Big O符号（可能[在这里]（https://en.wikipedia.org/wiki/Big_O_notation））。在这种特殊情况下，粗略地说，这意味着算法运行时所需的内存与两个字符串长度的乘积成正比， –

设计一个算法，计算两个字符串之间的编辑距离

回答

相关问题