JavaScript में दो सरणियों में सबसे लंबी सामान्य श्रृंखला (Common Streak) ढूंढना

हमें एक JavaScript फ़ंक्शन लिखना है जो शाब्दिक मूल्यों की दो सरणियाँ लेता है, आइए उन्हें arr1 और arr2 कहते हैं।

फ़ंक्शन को सरणियों में शाब्दिक मूल्यों की सबसे लंबी सामान्य श्रृंखला ढूंढनी चाहिए। फ़ंक्शन को अंततः उन शाब्दिक मूल्यों की एक सरणी वापस करनी चाहिए।

उदाहरण के लिए -

यदि इनपुट सरणियाँ हैं -

const arr1 = ['a', 'b', 'c', 'd', 'e'];
const arr2 = ['k', 'j', 'b', 'c', 'd', 'w'];

तो आउटपुट सरणी होनी चाहिए -

const output = ['b', 'c', 'd'];

उदाहरण

निम्नलिखित कोड देखें:

const arr1 = ['a', 'b', 'c', 'd', 'e'];
const arr2 = ['k', 'j', 'b', 'c', 'd', 'w'];

const longestCommonSubsequence = (arr1 = [], arr2 = []) => {
  let str1 = arr1.join('');
  let str2 = arr2.join('');
  const arr = Array(str2.length + 1).fill(null).map(() => Array(str1.length + 1).fill(null));
  for (let j = 0; j <= str1.length; j += 1) {
    arr[0][j] = 0;
  }
  for (let i = 0; i <= str2.length; i += 1) {
    arr[i][0] = 0;
  }
  for (let i = 1; i <= str2.length; i += 1) {
    for (let j = 1; j <= str1.length; j += 1) {
      if (str1[j - 1] === str2[i - 1]) {
        arr[i][j] = arr[i - 1][j - 1] + 1;
      } else {
        arr[i][j] = Math.max(
          arr[i - 1][j],
          arr[i][j - 1]
        );
      }
    }
  }
  if (!arr[str2.length][str1.length]) {
    return [''];
  }
  const res = [];
  let j = str1.length;
  let i = str2.length;
  while (j > 0 || i > 0) {
    if (str1[j - 1] === str2[i - 1]) {
      res.unshift(str1[j - 1]);
      j -= 1;
      i -= 1;
    } else if (arr[i][j] === arr[i][j - 1]) {
      j -= 1;
    } else {
      i -= 1;
    }
  }
  return res;
};

console.log(longestCommonSubsequence(arr1, arr2));

आउटपुट

कंसोल पर निम्नलिखित आउटपुट प्राप्त होगा:

['b', 'c', 'd']