如何通过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>