Add longest common subsequence (thuva4#879)

thuva4 · web-flow · commit f81c8c5cb96f · 2021-10-02T08:37:51.000+05:30
* add js factorial

* fix tests

* add string partial sort

* add LongestCommonSubsequence in JS

Co-authored-by: Thuvarakan Tharmarajasingam &lt;thuva4.dev@gmail.com&gt;
diff --git a/algorithms/JavaScript/LongestCommonSubsequence/__tests__/index.test.js b/algorithms/JavaScript/LongestCommonSubsequence/__tests__/index.test.js
@@ -0,0 +1,20 @@
+const {lcs} = require('../index');
+
+describe("LongestCommonSubsequence", () => {
+
+  it("should return 0 if length is 0", () => {
+    expect(lcs("", "A")).toEqual(0);
+  });
+
+  it("should return 0 if the string is undefined", () => {
+    expect(lcs("A")).toEqual(0);
+  });
+
+  it("should return 0 if the string is undefined", () => {
+    expect(lcs("A", null)).toEqual(0);
+  });
+
+  it("should return correct value for valid strings", () => {
+    expect(lcs("AGGTAB", "GXTXAYB")).toEqual(4);
+  });
+});
diff --git a/algorithms/JavaScript/LongestCommonSubsequence/index.js b/algorithms/JavaScript/LongestCommonSubsequence/index.js
@@ -0,0 +1,26 @@
+const lcs = (string1, string2) => {
+  
+  if (!string1 || !string2) return 0;
+  
+  const string1Array = string1.split('');
+  const string2Array = string2.split('');
+
+  const dpArray = [];
+
+  string1Array.forEach(() => {
+    dpArray.push([]);
+  });
+
+  for (let i = 0; i< string1Array.length; i += 1) {
+    for (let j = 0; j< string2Array.length; j += 1) {
+      if (string1Array[i] === string2Array[j]) {
+        dpArray[i][j] = 1 + (dpArray[i-1]?.[j-1] ? dpArray[i-1][j-1] : 0)
+      } else {
+        dpArray[i][j] = Math.max(dpArray[i-1]?.[j] ? dpArray[i-1][j] : 0 , dpArray[i]?.[j-1] ? dpArray[i][j-1] : 0)
+      }
+    }
+  }
+  return dpArray[string1Array.length-1][string2Array.length-1]
+}
+
+module.exports = {lcs};
