如何通過Levenshtein算法（使用Javascript）使用動態編程

Question

我試圖通過Levenshtein算法瞭解動態編程，但我一直堅持這幾個小時。我知道我在以下問題上的嘗試是'蠻力'之一。我將如何使用「動態編程」來改變我的方法？我幾乎失去了....

問題：給定兩個字符串s和t，其中n和m的長度，創建一個 函數，返回下列字符串之一：「插入C」如果 字符串t可以通過插入字符C「刪除C」 （與上述相同的邏輯）「交換cd」來獲得，如果字符串t可以通過交換出現在 中的兩個相鄰字符（c和d）從 獲得字符串s在原始字符串中的順序。 「沒什麼」，如果沒有操作需要「不可能」 如果沒有上述作品即Levenshtein距離大於1

這裏是我的蠻力嘗試。 「tuple」變量的名稱是錯誤的，因爲我最初想將索引和值推送到矩陣中，但卻被卡住了。

function levenshtein(str1, str2) { 
    var m = str1.length, 
    n = str2.length, 
    d = [], 
    i, j, 
    vals = [], 
    vals2 = []; 


    for (i = 0; i <= m ; i++) { 

    var tuple = [str1[i]]; 
    //console.log(tuple); 
    // console.log(tuple); 
    d[i] = [i]; 
    // console.log(str1[i]); 
    vals.push(tuple); 

    } 
    vals = [].concat.apply([], vals); 
    vals = vals.filter(function(n){ return n; }); 
    console.log(vals); 

    for (j = 0; j <= n; j++) { 
    d[0][j] = j; 
    var tuple2 = [str2[j]]; 
    // console.log(tuple2); 
    vals2.push(tuple2); 
    // console.log(vals2); 
    } 


    vals2 = [].concat.apply([], vals2); 
    vals2 = vals2.filter(function(n){ return n ;}); 
    console.log(vals2); 
    for (j = 1; j <= n; j++) { 
    for (i = 1; i <= m; i++) { 
     if (str1[i - 1] == str2[j - 1]) d[i][j] = d[i - 1][j - 1]; 
     else d[i][j] = Math.min(d[i - 1][j], d[i][j - 1], d[i - 1][j - 1]) + 1; 
    } 
    } 
    var val = d[m][n]; 

    // console.log(d); 
    if(val > 1){ 
    return "IMPOSSIBLE"; 
    } 
    if(val === 0){ 
    return "NOTHING"; 
    } 
    //console.log(d); 
    if(val === 1){ 
    //find the missing element between the vals 

     //return "INSERT " + missing element 
    //find the extra element 
     //return "DELETE + " extra element 

    //find the out of place element and swap with another 
    } 

} 

console.log(levenshtein("kitten", "mitten")); 
// console.log(levenshtein("stop", "tops")); 

// console.log(levenshtein("blahblah", "blahblah")); 

Answer 1

所描述的問題不能使用動態規劃進行優化，因爲它只涉及單個決策而不是一系列決策。

請注意，問題明確指出當Levenshtein距離大於1時應該返回「不可能」，即通過單個操作不能使字符串相等。您需要搜索0或更多的序列操作累積如果您想要應用動態規劃，則會產生最佳解決方案。如果更改計算之間的全部編輯距離的問題（這是什麼the dynamic programming wikipedia article在談論當它說你需要「最優子」和的動態規劃「重疊子問題」是適用的。）

兩個字符串，那麼您可以使用動態編程進行優化，因爲您可以重複使用選擇的結果在字符串中的特定位置執行某些操作，以降低搜索的複雜性。

---

您當前的解決方案對於給定問題看起來有點過於複雜。以下簡單的方法可以學習。該解決方案利用了以下事實：您知道只能執行至多一次操作，並且可以基於兩個字符串的長度之間的差異來推斷要嘗試執行哪個操作。我們也知道，在兩個字符串不同的地方嘗試給定的操作，而不是在每個位置，都是有意義的。

function lev(s, t) { 
 
    // Strings are equal 
 
    if (s == t) return "nothing" 
 
    // Find difference in string lengths 
 
    var delta = s.length - t.length 
 
    // Explode strings into arrays 
 
    var arrS = s.split("") 
 
    var arrT = t.split("") 
 
    // Try swapping 
 
    if (delta == 0) { 
 
     for (var i=0; i<s.length; i++) { 
 
      if (arrS[i] != arrT[i]) { 
 
       var tmp = arrS[i] 
 
       arrS[i] = arrS[i+1] 
 
       arrS[i+1] = tmp 
 
       if (arrS.join("") == t) { 
 
        return "swap " + arrS[i+1] + " " + arrS[i] 
 
       } 
 
       else break 
 
      } 
 
     } 
 
    } 
 
    // Try deleting 
 
    else if (delta == 1) { 
 
     for (var i=0; i<s.length; i++) { 
 
      if (arrS[i] != arrT[i]) { 
 
       var c = arrS.splice(i, 1)[0] 
 
       if (arrS.join("") == t) { 
 
        return "delete " + c 
 
       } 
 
       else break 
 
      } 
 
     } 
 
    } 
 
    // Try inserting 
 
    else if (delta == -1) { 
 
     for (var i=0; i<t.length; i++) { 
 
      if (arrS[i] != arrT[i]) { 
 
       arrS.splice(i, 0, arrT[i]) 
 
       if (arrS.join("") == t) { 
 
        return "insert " + arrS[i] 
 
       } 
 
       else break 
 
      } 
 
     } 
 
    } 
 
    // Strings are too different 
 
    return "impossible" 
 
} 
 

 

 
// output helper 
 
function out(msg) { $("body").append($("<div/>").text(msg)) } 
 

 
// tests 
 
out(lev("kitten", "mitten")) 
 
out(lev("kitten", "kitten")) 
 
out(lev("kitten", "kitetn")) 
 
out(lev("kiten", "kitten")) 
 
out(lev("kitten", "kittn"))

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>