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))
1function longestCommonSubsequence(text1, text2) {
2 if (text1.length < text2.length) {
3 [text1, text2] = [text2, text1];
4 }
5 const n = text1.length;
6 const m = text2.length;
7
8 let previous = Array(m + 1).fill(0);
9 let current = Array(m + 1).fill(0);
10
11 for (let i = 1; i <= n; i++) {
12 current.fill(0);
13 for (let j = 1; j <= m; j++) {
14 if (text1[i - 1] === text2[j - 1]) {
15 current[j] = previous[j - 1] + 1;
16 } else {
17 current[j] = Math.max(previous[j], current[j - 1]);
18 }
19 }
20 [previous, current] = [current, previous];
21 }
22
23 return previous[m];
24}
25
26console.log(longestCommonSubsequence("abcde", "ace"));The JavaScript solution effectively reduces the space requirement by using two arrays and iteratively swapping them, allowing for space-efficient storage of LCS computation. This makes it suitable for handling larger input sizes within a limited space budget.