문제 설명
재귀 대신 동적 프로그래밍을 사용하여 가장 큰 공통 접미사(자바스크립트) 찾기 (Use dynamic programming instead of recursion to find largest common suffix (javascript))
두 문자열의 가장 큰 공통 접미사를 찾는 재귀 솔루션을 찾았습니다. 이것을 동적 프로그래밍 솔루션으로 어떻게 변환할 수 있습니까? 접미사는 두 문자열의 끝에서 비교하는 것이 가장 쉽기 때문에 상향식 솔루션을 개념화하기가 어렵습니다. 솔루션을 시도했지만 나에게 하향식인 것 같습니다.
ATTEMPT
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'));
RECURSIVE
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 '';
}
};
참조 솔루션
방법 1:
Try like this
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;
}
DEMO HERE
(by Daniel Kobe、RiccardoC)