feat: Added Longest Common Subsequence (TheAlgorithms#173)

Suryac72 · web-flow · commit b1094362e92e · 2023-10-05T15:33:31.000+05:30
diff --git a/dynamic_programming/lcs.ts b/dynamic_programming/lcs.ts
@@ -0,0 +1,46 @@
+/**
+ * Find the Longest Common Subsequence (LCS) of two strings.
+ * @param text1 - The first input string.
+ * @param text2 - The second input string.
+ * @returns The longest common subsequence as a string.
+ */
+
+export const  longestCommonSubsequence = (text1: string, text2: string): string => {
+    const m = text1.length;
+    const n = text2.length;
+  
+    // Create a 2D array to store the lengths of LCS
+    const dp: number[][] = Array.from({ length: m + 1 }, () =>
+      Array(n + 1).fill(0)
+    );
+  
+    // Fill in the DP table
+    for (let i = 1; i <= m; i++) {
+      for (let j = 1; j <= n; j++) {
+        if (text1[i - 1] === text2[j - 1]) {
+          dp[i][j] = dp[i - 1][j - 1] + 1;
+        } else {
+          dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
+        }
+      }
+    }
+  
+    // Reconstruct the LCS from the DP table
+    let i = m;
+    let j = n;
+    const lcs: string[] = [];
+    while (i > 0 && j > 0) {
+      if (text1[i - 1] === text2[j - 1]) {
+        lcs.unshift(text1[i - 1]);
+        i--;
+        j--;
+      } else if (dp[i - 1][j] > dp[i][j - 1]) {
+        i--;
+      } else {
+        j--;
+      }
+    }
+  
+    return lcs.join('');
+  }
+  
diff --git a/dynamic_programming/test/lcs.test.ts b/dynamic_programming/test/lcs.test.ts
@@ -0,0 +1,28 @@
+import { longestCommonSubsequence } from "../lcs";
+
+describe("longestCommonSubsequence", () => {
+  it("should return the longest common subsequence", () => {
+    expect(longestCommonSubsequence("ABCD", "ACDF")).toBe("ACD");
+
+    expect(longestCommonSubsequence("AGGTAB", "GXTXAYB")).toBe("GTAB");
+
+    expect(longestCommonSubsequence("abcdef", "xyz")).toBe("");
+
+    expect(longestCommonSubsequence("", "")).toBe("");
+  });
+
+  it("should handle cases with spaces and special characters", () => {
+    expect(longestCommonSubsequence("A B C D", "A C D E")).toBe("A C D");
+
+    expect(longestCommonSubsequence("1234$%^", "!@#$%^")).toBe("$%^");
+  });
+
+  it("should handle cases with longer input strings", () => {
+    expect(
+      longestCommonSubsequence(
+        "Lorem ipsum dolor sit amet, consectetur adipiscing elit.",
+        "Sed do eiusmod tempor incididunt ut labore et dolore magna aliqua."
+      )
+    ).toBe("e iumoor it t oeetr ag li.");
+  });
+});
