How to use Memoization (Top-Down Dynamic Programming) In Javascript
In this approach, we’ll use memoization to efficiently solve the problem by storing the results of previously solved subproblems.
- Create a memoization table (an array of arrays) to store the length of the LCS for different prefixes of the two strings.
- Define a recursive function to compute the LCS of two substrings, considering all possible cases.
- Use memoization to avoid redundant calculations by storing the results of subproblems in the memoization table.
- The base cases for the recursion are when either of the strings becomes empty. In such cases, the length of the LCS is 0.
- If the characters at the current positions in both strings match, we include this character in the LCS and recursively compute the LCS for the remaining substrings.
- If the characters don’t match, we consider two possibilities: either excluding the current character from the first string or excluding it from the second string, and we take the maximum of the lengths of the LCS obtained from these two possibilities.
- Finally, return the length of the LCS, which is stored in the memoization table.
Here’s the implementation in JavaScript:
function findLCS(s1, s2) {
const memo = new Array(s1.length + 1).fill(null).map(() => new Array(s2.length + 1).fill(-1));
function lcsHelper(i, j) {
if (i === 0 || j === 0) return 0;
if (memo[i][j] !== -1) return memo[i][j];
if (s1[i - 1] === s2[j - 1])
memo[i][j] = 1 + lcsHelper(i - 1, j - 1);
else
memo[i][j] = Math.max(lcsHelper(i - 1, j), lcsHelper(i, j - 1));
return memo[i][j];
}
lcsHelper(s1.length, s2.length);
let i = s1.length, j = s2.length;
let lcs = "";
while (i > 0 && j > 0) {
if (s1[i - 1] === s2[j - 1]) {
lcs = s1[i - 1] + lcs;
i--;
j--;
} else if (memo[i - 1][j] > memo[i][j - 1])
i--;
else
j--;
}
return lcs;
}
// Test Case
const s1 = "ABCDEK";
const s2 = "BDEGK";
console.log("Longest Common Subsequence: " + findLCS(s1, s2)); // Output: ABF
Output
Longest Common Subsequence: BDEK
JavaScript Program for Longest Common Subsequence
The longest common subsequence (LCS) is defined as the longest subsequence which is common in all given input sequences. In this article, we are given two strings, String1 and String2, the task is to find the longest common subsequence in both of the strings. A subsequence of a string can be achieved by deleting any number of elements from the string.
Example:
Input: 'ABCD' , 'AEBECED'
Output: 'ABCD'
Explanation: As 'ABCD' is common in both of the string and it is the longest string.
Table of Content
- Brute force Method
- Using DP array
- Using Memoization (Top-Down Dynamic Programming)