- Get link
- Other Apps
Featured Post
Posted by
Varun
on
- Get link
- Other Apps
Longest Common Subsequence (LCS)
- It's the longest sequence of characters that is present in the same relative order within two or more strings.
- It doesn't have to be a contiguous substring; the characters can appear in different positions within the original strings.
Understanding the Problem
- Imagine two strings, written vertically on separate columns.
- The goal is to find the longest sequence of characters that appears in the same order within both strings, even if they're not consecutive.
Character Grid
- Create a grid where each row represents a character from the first string, and each column represents a character from the second string.
- Fill each cell with a color indicating whether the corresponding characters match (e.g., green) or not (e.g., white).
Tracing Paths
- Start at the top-left corner of the grid.
- Move diagonally down-right only when characters match (green cells).
- If characters don't match, move either down or right to continue searching for matches.
- The path you take represents the LCS.
Visualize the LCS
- Highlight the cells along the longest path with a bolder color or border.
- The characters in those cells, read in order, form the LCS.
Example:
Consider strings "AGGTAB" and "GXTXAYB":
Algorithm
Dynamic Programming Table:
- Create a 2D table
dp
with dimensions (m+1) x (n+1), where m and n are the lengths of the two strings. - Fill the first row and column with 0s, indicating no LCS for empty strings.
- Create a 2D table
Filling the Table:
- Iterate through the table, starting from
dp[1][1]
. - For each cell
dp[i][j]
:- If the characters at indices i-1 and j-1 in the strings match:
- Set
dp[i][j] = dp[i-1][j-1] + 1
(add 1 to the LCS length of the previous substrings).
- Set
- Else:
- Set
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
(take the maximum LCS length from the previous options).
- Set
- If the characters at indices i-1 and j-1 in the strings match:
- Iterate through the table, starting from
Reconstructing the LCS:
- Start from the bottom-right corner of the table (
dp[m][n]
). - Backtrack:
- If the characters at indices i-1 and j-1 match, add the character to the LCS and move diagonally up (i--, j--).
- Else, move to the cell with the maximum value (either i-- or j--).
- Reverse the constructed LCS string to get the correct order.
- Start from the bottom-right corner of the table (
public class LCS {
public static String lcs(String str1, String str2) {
int m = str1.length();
int n = str2.length();
int[][] dp = new int[m + 1][n + 1];
// Build the table in a bottom-up manner
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// Reconstruct the LCS
StringBuilder lcs = new StringBuilder();
int i = m, j = n;
while (i > 0 && j > 0) {
if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
lcs.append(str1.charAt(i - 1));
i--;
j--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
i--;
} else {
j--;
}
}
// Reverse the LCS string
return lcs.reverse().toString();
}
// Example usage for testing
public static void main(String[] args) {
System.out.println(lcs("ABCDEFG", "BCDGK"));
System.out.println(lcs("AGGTAB", "GXTXAYB"));
System.out.println(lcs("ABCDE", "A"));
System.out.println(lcs("A", "BCDEF"));
}
}
Explanation for code
1. lcs() Method:
- Takes two strings as input.
- Uses dynamic programming to find the longest common subsequence (LCS).
- Returns the LCS string.
Steps
- Create a DP Table: Stores the lengths of LCSs for substrings of different lengths.
- Fill the DP Table:
- Iterates through characters of both strings.
- For each cell, calculates the length of the LCS based on previous calculations:
- If characters match, add 1 to the LCS length of the previous substrings.
- If not, take the maximum LCS length from the previous options.
- Reconstruct the LCS: Backtracks through the DP table to find the characters in the LCS.
- Reverse the LCS: Since it's built backward, reverse it before returning.
Take away points
- Bottom-up approach: Builds the solution from smaller subproblems to the final LCS.
- Dynamic programming principle: Avoids redundant calculations by storing intermediate results.
- Time complexity: O(mn), where m and n are string lengths.
- Space complexity: O(mn), due to the DP table.
backtracking
bottom-up approach
lcs dynamic programming table
LCS problem
longest common subsequence algorithm
optimal solution
reconstruction
space complexity
string algorithms
time complexity
- Get link
- Other Apps
Comments
Post a Comment
Please post your valuable suggestions