我試圖通過Levenshtein算法瞭解動態編程,但我一直堅持這幾個小時。我知道我在以下問題上的嘗試是'蠻力'之一。我將如何使用「動態編程」來改變我的方法?我幾乎失去了....如何通過Levenshtein算法(使用Javascript)使用動態編程
問題:給定兩個字符串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"));
哇,太神奇了謝謝。所以我並不需要所有這些矩陣...... – devdropper87