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))
1class Solution {
2 public int longestCommonSubsequence(String text1, String text2) {
3 int n = text1.length();
4 int m = text2.length();
5 if (n < m) {
6 String temp = text1;
7 text1 = text2;
8 text2 = temp;
9 n = text1.length();
10 m = text2.length();
11 }
12 int[] previous = new int[m + 1];
13 int[] current = new int[m + 1];
14
15 for (int i = 1; i <= n; i++) {
16 for (int j = 1; j <= m; j++) {
17 if (text1.charAt(i-1) == text2.charAt(j-1))
18 current[j] = previous[j-1] + 1;
19 else
20 current[j] = Math.max(previous[j], current[j-1]);
21 }
22 int[] temp = previous;
23 previous = current;
24 current = temp;
25 }
26 return previous[m];
27 }
28
29 public static void main(String[] args) {
30 Solution sol = new Solution();
31 System.out.println(sol.longestCommonSubsequence("abcde", "ace"));
32 }
33}The Java implementation also follows similar optimization techniques, using two one-dimensional arrays and swapping them iteratively. This reduces space complexity substantially without compromising on ease of implementation or time efficiency.