Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // LCS Solution 1
- function longestCommonSubsequence(xString, yString) {
- function recur(xArray, yArray, lcs) {
- var xElement = xArray[0];
- var yElement = yArray[0];
- // Base case --> out of string!
- // return the LCS of this section
- if (!xElement || !yElement) {
- return lcs;
- }
- // First Property
- if (xElement === yElement) {
- // append element to Subseq
- // remove element from each array
- // find LCS of remaining section
- return recur(xArray.slice(1), yArray.slice(1), lcs += xElement);
- }
- // Second Property
- if (xElement !== yElement) {
- // return the larger of the following cases:
- // Case 1, the LCS does not end in xElement
- var case1 = recur(xArray.slice(1), yArray, lcs);
- // Case 2, the LCS does not end in yElement
- var case2 = recur(xArray, yArray.slice(1), lcs);
- return case1.length > case2.length ? case1 : case2;
- }
- }
- return recur(xString, yString, '');
- }
- // LCS Solution #2
- function longestCommonSubsequence2(xString, yString) {
- // Base case --> empty string
- if (xString === '' || yString === '') {
- return '';
- }
- // grab the first element
- var xElement = xString.charAt(0);
- var yElement = yString.charAt(0);
- // First Property: elements match
- if (xElement === yElement) {
- // return element + the LCS of remaining sections
- return xElement + longestCommonSubsequence2(xString.slice(1), yString.slice(1));
- }
- // Second Property: elements do not match
- // return the longer of the following cases:
- // Case 1, the LCS does not begin in xElement
- var case1 = longestCommonSubsequence2(xString.slice(1), yString);
- // Case 2, the LCS does not end in yElement
- var case2 = longestCommonSubsequence2(xString, yString.slice(1));
- return case1.length > case2.length ? case1 : case2;
- }
- console.log("1a", longestCommonSubsequence("a", "b")); // ""
- console.log("2a", longestCommonSubsequence2("a", "b")); // ""
- console.log("1c", longestCommonSubsequence("BANANA", "ATANA")); // "AANA"
- console.log("2c", longestCommonSubsequence2("BANANA", "ATANA")); // "AANA"
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement