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.
1class Solution {
2 public int longestCommonSubsequence(String text1, String text2) {
3 int n = text1.length();
4 int m = text2.length();
5 int[][] dp = new int[n+1][m+1];
6
7 for (int i = 1; i <= n; i++) {
8 for (int j = 1; j <= m; j++) {
9 if (text1.charAt(i-1) == text2.charAt(j-1))
10 dp[i][j] = dp[i-1][j-1] + 1;
11 else
12 dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
13 }
14 }
15
16 return dp[n][m];
17 }
18
19 public static void main(String[] args) {
20 Solution sol = new Solution();
21 System.out.println(sol.longestCommonSubsequence("abcde", "ace"));
22 }
23}This Java solution uses a class Solution with a method longestCommonSubsequence to populate a 2D array dp for LCS calculation. The method compares the characters from the strings and uses a standard dynamic programming approach as discussed earlier.
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))
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 if (n < m) {
8 var tempStr = text1;
9 text1 = text2;
10 text2 = tempStr;
11 n = text1.Length;
12 m = text2.Length;
13 }
14 int[] previous = new int[m + 1];
15 int[] current = new int[m + 1];
16
17 for (int i = 1; i <= n; i++) {
18 for (int j = 1; j <= m; j++) {
19 if (text1[i - 1] == text2[j - 1])
20 current[j] = previous[j - 1] + 1;
21 else
22 current[j] = Math.Max(previous[j], current[j - 1]);
23 }
24 var temp = previous;
25 previous = current;
26 current = temp;
27 }
28 return previous[m];
29 }
30
31 public static void Main() {
32 Solution sol = new Solution();
33 Console.WriteLine(sol.LongestCommonSubsequence("abcde", "ace"));
34 }
35}The C# implementation follows the pattern of utilizing only two arrays and swapping between them to reduce space complexity while maintaining comprehensive and easily understandable logic to compute LCS.