使用动态规划而不是递归来查找最大公共后缀 (javascript)
Use dynamic programming instead of recursion to find largest common suffix (javascript)
我找到了一个递归解决方案来查找两个字符串的最大公共后缀。如何将其转换为动态编程解决方案。我很难概念化自下而上的解决方案,因为后缀最容易从两个字符串的末尾进行比较。我有一个尝试过的解决方案,但对我来说似乎是自上而下的。
尝试
var LCSuffDyn = function(X,Y) {
longest_suffix = [''];
var largest_string, smallest_string;
if (X.length > Y.length) {
largest_string = X;
smallest_string = Y;
} else {
largest_string = Y;
smallest_string = X;
}
for (var k=1; k<smallest_string.length; k++) {
if (X[X.length-k] === Y[Y.length-k]) {
longest_suffix[k] = X[X.length-k]+longest_suffix[k-1];
}
else break;
}
return longest_suffix[longest_suffix.length-1];
};
console.log(LCSuffDyn('cbbbbbbbbbbajlbbbbbbbaba', 'cajkbbbbbbbbbjklbaba'));
递归
var LCSuffRec = function(X,Y) {
return rec(X,Y, X.length, Y.length);
function rec(X, Y, m, n) {
if (X[m-1] === Y[n-1]) return rec(X, Y, m-1, n-1) + X[m-1];
else return '';
}
};
这样试试
function LCSuffDyn( X, Y ) {
var result = "";
var indexX = X.length - 1;
var indexY = Y.length - 1;
var endIt = false;
while( indexX >= 0 && indexY >= 0 && !endIt ) {
if( X.substr( indexX, 1 ) == Y.substr( indexY, 1 ) ) {
result = X.substr( indexX, 1 ) + result;
} else {
endIt = true;
}
indexX --;
indexY --;
}
return result;
}
演示版HERE
我找到了一个递归解决方案来查找两个字符串的最大公共后缀。如何将其转换为动态编程解决方案。我很难概念化自下而上的解决方案,因为后缀最容易从两个字符串的末尾进行比较。我有一个尝试过的解决方案,但对我来说似乎是自上而下的。
尝试
var LCSuffDyn = function(X,Y) {
longest_suffix = [''];
var largest_string, smallest_string;
if (X.length > Y.length) {
largest_string = X;
smallest_string = Y;
} else {
largest_string = Y;
smallest_string = X;
}
for (var k=1; k<smallest_string.length; k++) {
if (X[X.length-k] === Y[Y.length-k]) {
longest_suffix[k] = X[X.length-k]+longest_suffix[k-1];
}
else break;
}
return longest_suffix[longest_suffix.length-1];
};
console.log(LCSuffDyn('cbbbbbbbbbbajlbbbbbbbaba', 'cajkbbbbbbbbbjklbaba'));
递归
var LCSuffRec = function(X,Y) {
return rec(X,Y, X.length, Y.length);
function rec(X, Y, m, n) {
if (X[m-1] === Y[n-1]) return rec(X, Y, m-1, n-1) + X[m-1];
else return '';
}
};
这样试试
function LCSuffDyn( X, Y ) {
var result = "";
var indexX = X.length - 1;
var indexY = Y.length - 1;
var endIt = false;
while( indexX >= 0 && indexY >= 0 && !endIt ) {
if( X.substr( indexX, 1 ) == Y.substr( indexY, 1 ) ) {
result = X.substr( indexX, 1 ) + result;
} else {
endIt = true;
}
indexX --;
indexY --;
}
return result;
}
演示版HERE