Sponsored
Sponsored
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
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))
public class Solution {
public int LongestCommonSubsequence(string text1, string text2) {
int n = text1.Length;
int m = text2.Length;
if (n < m) {
var tempStr = text1;
text1 = text2;
text2 = tempStr;
n = text1.Length;
m = text2.Length;
}
int[] previous = new int[m + 1];
int[] current = new int[m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (text1[i - 1] == text2[j - 1])
current[j] = previous[j - 1] + 1;
else
current[j] = Math.Max(previous[j], current[j - 1]);
}
var temp = previous;
previous = current;
current = temp;
}
return previous[m];
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.LongestCommonSubsequence("abcde", "ace"));
}
}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.