Find the Longest Common Subsequence Between Two Strings
Sat Mar 16 2024 compareArray :
A crucial function that identifies the LCS between two strings. It taps into the power of subsequences generated from both strings, using a Map for efficient tracking and comparison. This mechanism not only facilitates the search for common subsequences but also ensures the longest one is found, showcasing the essence of optimal string analysis.
stringSubsequence :
The backbone of our LCS finder, this recursive function meticulously generates every possible subsequence from a given string. Through a dual-path approach of including or excluding characters, it lays down an extensive list of subsequences. This groundwork is vital for the compareArray function, enabling a thorough comparison to unearth the LCS.
1let element1 = [];
2let element2 = [];
3
4let str1 = "ABCDGH";
5let str2 = "AEDFHR";
6function stringSubsequence(input, output, element) {
7 if (input.length === 0) {
8 element.push(output);
9 return;
10 }
11 stringSubsequence(input.substring(1), output, element);
12 stringSubsequence(input.substring(1), output + input[0], element);
13}
14
15function compareArray(str1, str2) {
16 let arr1 = [];
17 let arr2 = [];
18 stringSubsequence(str1, "", arr1);
19 stringSubsequence(str2, "", arr2);
20 let m = new Map();
21 for (let i = 0; i < arr1.length; i++) {
22 m.set(arr1[i], arr1[i].length);
23 }
24 let maxLength = -Infinity;
25 for (let i = 0; i < arr2.length; i++) {
26 if (m.has(arr2[i])) {
27 if (m.get(arr2[i]) > maxLength) {
28 maxLength = m.get(arr2[i]);
29 }
30 }
31 }
32 return maxLength;
33}
34console.log(compareArray(str1, str2));
35