I'm trying to understand dynamic programming through Levenshtein algorithm, but I have been stuck on this for a few hours now. I know my attempt at the following problem is the 'brute force' one. How would I use "dynamic programming" to change my approach? I'm pretty lost....
Problem: Given two strings, s and t, with lengths of n and m, create a function that returns one of the following strings: "insert C" if string t can be obtained from s by inserting character C "delete C" (same logic as above) "swap c d" if string t can be obtained from string s by swapping two adjacent characters (c and d) which appear in that order in the original string. "Nothing" if no operation is needed "impossible" if none of the above works ie LevenShtein distance is greater than 1.
Here is my brute force attempt. the "tuple" variable is misnamed as I originally wanted to push the indices and values to the matrix but got stuck on that.
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"));
The problem as described cannot be optimized using dynamic programming because it only involves a single decision, not a series of decisions.
Note that the problem specifically states that you should return "impossible" when the Levenshtein distance is greater than 1, i.e., the strings can't be made equal through a single operation. You need to be searching for a sequence of zero or more operations that cumulatively result in the optimal solution if you want to apply dynamic programming. (This is what the dynamic programming wikipedia article is talking about when it says you need "optimal substructure" and "overlapping subproblems" for dynamic programming to be applicable.)
If you change the problem to calculate the full edit distance between two strings, then you can optimize using dynamic programming because you can reuse the result of choosing to do certain operations at a particular location in the string in order to reduce the complexity of the search.
Your current solution looks a bit overly complex for the given problem. Below a simpler approach you can study. This solution takes advantage of the fact that you know you can only do at most one operation, and you can infer which operation to attempt based off the difference between the lengths of the two strings. We also know that it only makes sense to try the given operation at the point where the two strings differ, rather than at every position.
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>