設計一個算法，計算兩個字符串之間的編輯距離

-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））。在這種特殊情況下，粗略地說，這意味着算法運行時所需的內存與兩個字符串長度的乘積成正比， –

設計一個算法，計算兩個字符串之間的編輯距離

回答

相關問題