Finding the Longest Common Subsequence (LCS) of Two Strings
Mastering The LCS Problem in JavaScript
--
JavaScript Challenges: Beginner to Master — Task #52
Create a function that finds the two strings' longest common subsequence (LCS). The function should take two strings as input and return the LCS. The LCS is the longest sequence of characters that appear in both strings in the same order.
LCS — Longest Common Subsequence
This is a classic problem in computer science and dynamic programming.
Given two sequences (or strings), the goal is to find the length of the longest subsequence present in both of them.
A subsequence is a sequence that appears in the same relative order but not necessarily consecutively.
Step-by-Step Solution of Task #52
Step 1: Define the LCS Function
Begin by defining our final function, called longestCommonSubsequence that accepts two string arguments: s1 and s2. When complete, it will return the LCS of the input strings.
function longestCommonSubsequence(s1, s2) { ... }Step 2: Initialize String Length Variables
Add two lines of code to fetch the lengths of the strings s1 and s2 and store them in variables m and n, respectively.
const m = s1.length;
const n = s2.length;This helps you by looping through each string and setting up the dynamic programming table.
Step 3: Set Up the Dynamic Programming Table
Since you need a 2D array that is initialized by the variable dp where dp[i][j] represents the length of the LCS between the first i characters of s1 and the first j characters of s2.
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));The +1 size ensures that you can also handle empty substrings.
Each cell is initialized to zero as a starting point.
