longestCommonSubsequenceRecursive.js

/* eslint-disable no-param-reassign */
/**
 * Longest Common Subsequence (LCS) (Recursive Approach).
 *
 * @param {string} string1
 * @param {string} string2
 * @return {number}
 */
export default function longestCommonSubsequenceRecursive(string1, string2) {
  /**
   *
   * @param {string} s1
   * @param {string} s2
   * @return {string} - returns the LCS (Longest Common Subsequence)
   */
  const lcs = (s1, s2, memo = {}) => {
    if (!s1 || !s2) return '';

    if (memo[`${s1}:${s2}`]) return memo[`${s1}:${s2}`];

    if (s1[0] === s2[0]) {
      return s1[0] + lcs(s1.substring(1), s2.substring(1), memo);
    }

    const nextLcs1 = lcs(s1.substring(1), s2, memo);
    const nextLcs2 = lcs(s1, s2.substring(1), memo);

    const nextLongest = nextLcs1.length >= nextLcs2.length ? nextLcs1 : nextLcs2;

    memo[`${s1}:${s2}`] = nextLongest;

    return nextLongest;
  };

  return lcs(string1, string2);
}