This approach uses dynamic programming to solve the problem by creating a 2D table to store the lengths of the longest common subsequences for different substrings. Each cell dp[i][j] in the table represents the longest common subsequence length of substrings text1[0..i-1] and text2[0..j-1]. The table is filled using the following rules:
text1[i-1] and text2[j-1] are equal, then dp[i][j] = dp[i-1][j-1] + 1.dp[i][j] = max(dp[i-1][j], dp[i][j-1]).The final answer is dp[text1.length][text2.length].
Time Complexity: O(n*m), where n and m are the lengths of text1 and text2 respectively.
Space Complexity: O(n*m) for the DP table.
1using System;
2
3public class Solution {
4 public int LongestCommonSubsequence(string text1, string text2) {
5 int n = text1.Length;
6 int m = text2.Length;
7 int[,] dp = new int[n + 1, m + 1];
8
9 for (int i = 1; i <= n; i++) {
10 for (int j = 1; j <= m; j++) {
11 if (text1[i - 1] == text2[j - 1])
12 dp[i, j] = dp[i - 1, j - 1] + 1;
13 else
14 dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
15 }
16 }
17
18 return dp[n, m];
19 }
20
21 public static void Main() {
22 Solution sol = new Solution();
23 Console.WriteLine(sol.LongestCommonSubsequence("abcde", "ace"));
24 }
25}This C# solution computes the longest common subsequence by defining an integer matrix dp, using a similar dynamic programming approach. The Main method shows how the LongestCommonSubsequence method can be used with example input.
This optimization reduces space complexity by only storing data for the current and the previous row. The idea remains the same - calculating the LCS length incrementally using a dynamic programming strategy. However, instead of a full 2D table, only two 1D arrays are used, effectively reducing space usage from O(n*m) to O(min(n, m)). This is achieved by noting that each row of the DP table depends only on the previous row. So, we use two arrays that swap every iteration.
Time Complexity: O(n*m), where n is the length of text1 and m is the length of text2.
Space Complexity: O(min(n, m))
1#include <stdio.h>
2#include <string.h>
3
4int longestCommonSubsequence(char* text1, char* text2) {
5 int n = strlen(text1);
6 int m = strlen(text2);
7 if (n < m) {
8 return longestCommonSubsequence(text2, text1);
9 }
10 int previous[m + 1];
11 int current[m + 1];
12 memset(previous, 0, sizeof(previous));
13
14 for (int i = 1; i <= n; i++) {
15 memset(current, 0, sizeof(current));
16 for (int j = 1; j <= m; j++) {
17 if (text1[i-1] == text2[j-1])
18 current[j] = previous[j-1] + 1;
19 else
20 current[j] = (previous[j] > current[j-1]) ? previous[j] : current[j-1];
21 }
22 memcpy(previous, current, sizeof(current));
23 }
24 return previous[m];
25}
26
27int main() {
28 char text1[] = "abcde";
29 char text2[] = "ace";
30 printf("%d\n", longestCommonSubsequence(text1, text2));
31 return 0;
32}The optimized C solution uses two arrays previous and current to store the LCS length for the current and last iteration. After computing each row, the current becomes the previous, thereby saving space. The solution is efficient both in terms of time and space compared to the full 2D table.