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.
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 int dp[n+1][m+1];
8 memset(dp, 0, sizeof(dp));
9
10 for (int i = 1; i <= n; i++) {
11 for (int j = 1; j <= m; j++) {
12 if (text1[i-1] == text2[j-1])
13 dp[i][j] = dp[i-1][j-1] + 1;
14 else
15 dp[i][j] = (dp[i-1][j] > dp[i][j-1]) ? dp[i-1][j] : dp[i][j-1];
16 }
17 }
18
19 return dp[n][m];
20}
21
22int main() {
23 char text1[] = "abcde";
24 char text2[] = "ace";
25 printf("%d\n", longestCommonSubsequence(text1, text2));
26 return 0;
27}This C solution defines a function longestCommonSubsequence that calculates the longest common subsequence length using a 2D array dp. The program iteratively updates the table based on character matches and topological decision making (max operation). The main function demonstrates this by testing with two example strings and printing the result.
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))
1def longest_common_subsequence(text1, text2):
2 if len(text1) < len(text2):
3 text1, text2 = text2, text1
4 n, m = len(text1), len(text2)
5
6 previous = [0] * (m + 1)
7 current = [0] * (m + 1)
8
9 for i in range(1, n + 1):
10 for j in range(1, m + 1):
11 if text1[i - 1] == text2[j - 1]:
12 current[j] = previous[j - 1] + 1
13 else:
14 current[j] = max(previous[j], current[j - 1])
15 previous, current = current, previous
16
17 return previous[m]
18
19print(longest_common_subsequence("abcde", "ace"))This Python solution efficiently reduces space usage by keeping data for the previous and the current row only, effectively moving the comparison outcome and using list swapping. This process is consistent with the previous solutions while being concise in Python.