In the field of computer science, string processing has always been an important research direction. Among them, the Longest Common Subsequence (LCS) is a classic string problem and has wide application and important theoretical value.
Today, we will explore the longest public subsequence problem in depth, analyze its concept, brute force solution, dynamic programming solution in detail, and provide Java code implementation.
Overview of the longest common subsequence problem
The longest common subsequence refers to finding the longest common subsequence between two strings or arrays. It should be noted that subsequences do not require continuity, as long as the relative order of elements remains consistent.
For example, for the strings "ABC" and "ABD", their longest common subsequence is "AB".
Problem understanding and example analysis
To better understand this problem, let's look at a few examples.
- For the strings "3563243" and "5134", their longest common subsequence is "534".
- Look at the strings "ABC34" and "A1BC2", and the longest common subsequence is "ABC".
- While the strings "123" and "456", the longest common subsequence is an empty set.
Violent solution ideas and example code
Violence method is a basic idea to solve the problem of the longest public subsequence. The core idea is to find all common subsequences of two strings and then find the longest one from them.
The specific implementation steps are as follows:
- Taking one of the strings (assuming S1) as the benchmark, use each character to header and try to find the common subsequence with the other string (S2).
- When the first identical character is found, it is taken as the beginning of the common subsequence, and then recursively calculates the common subsequence of the subsequent parts.
- Compare all the found common subsequences to find the longest one.
The following is the Java code implementation of the brute-force solution:
import ;
import ;
public class LongestCommonSubsequenceBruteForce {
public static List<String> findLCS(String s1, String s2) {
List<String> result = new ArrayList<>();
for (int i = 0; i < (); i++) {
char c = (i);
for (int j = 0; j < (); j++) {
if (c == (j)) {
String common = findCommon((i), (j));
if (() > 0) {
(c + common);
}
}
}
}
return result;
}
private static String findCommon(String s1, String s2) {
if (() || ()) {
return "";
}
if ((0) == (0)) {
return (0) + findCommon((1), (1));
} else {
String common1 = findCommon(s1, (1));
String common2 = findCommon((1), s2);
return () > ()? common1 : common2;
}
}
}However, the brute force solution is less efficient in practical applications because it requires computing all possible subsequences and has a high time complexity. When the string length is longer, the amount of calculation increases dramatically.
Dynamic programming solution
Dynamic programming is a more efficient way to solve the problem of longest common subsequences. The core idea is to record the solutions to subproblems by constructing a two-dimensional array (DP table) to avoid repeated calculations.
Construction and significance of DP table
The cells of the DP table represent the length of the longest common subsequence in the range of the current two substrips. The process of building a DP table is as follows:
- Initialize the first row and the first column: 1 if the current characters are equal; otherwise, 0.
- For other cells, consider the following three cases:
- If the two new characters appear the same, the value of the current cell is the value of the upper left cell plus 1.
- If it is different, take the maximum value in the left cell and the upper cell.
Dynamic programming solution process and code implementation
The following is a Java code implementation that uses dynamic programming to solve the longest common subsequence problem:
public class LongestCommonSubsequenceDP {
public static int findLCSLength(String s1, String s2) {
int m = ();
int n = ();
int[][] dp = new int[m + 1][n + 1];
// Initialize the first row and the first column for (int i = 0; i <= m; i++) {
dp[i][0] = 0;
}
for (int j = 0; j <= n; j++) {
dp[0][j] = 0;
}
// Fill in the DP table for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if ((i - 1) == (j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = (dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
}Backtracking to obtain the longest common subsequence
After getting the DP table, we also need to get the longest common subsequence through backtracking. The backtracking process starts from the lower right corner of the DP table, and determines the characters in the longest common subsequence based on the relationship between the value of the cell and the values of the left and upper cells.
The following is the Java code implementation for backtracking to get the longest common subsequence:
public class LongestCommonSubsequenceDP {
// The previous findLCSLength method
public static String findLCS(String s1, String s2) {
int m = ();
int n = ();
int[][] dp = new int[m + 1][n + 1];
// Code for initializing and populating DP table (same as before)
StringBuilder lcs = new StringBuilder();
int i = m, j = n;
while (i > 0 && j > 0) {
if ((i - 1) == (j - 1)) {
(0, (i - 1));
i--;
j--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
i--;
} else {
j--;
}
}
return ();
}
}Time and space complexity analysis of dynamic programming solutions
- Time complexity: The time complexity of the dynamic programming solution is O(m*n), where m and n are the lengths of two strings respectively. This is because we need to populate a DP table with m+1 row n+1 columns.
- Space complexity: The space complexity is also O(m*n), which is mainly used to store DP tables. However, if only the length of the longest common subsequence is required to be calculated, the spatial complexity can be reduced to O(min(m,n)) by optimization.
Summary and prospect
Through in-depth discussion of the longest common subsequence problem, we understand the ideas and implementation methods of brute force solutions and dynamic programming solutions. Although the brute force solution is simple and direct, it is less efficient when processing large-scale data. The dynamic programming solution significantly improves the computing efficiency by utilizing the overlapping properties of subproblems.
In practical applications, the longest common subsequence problem has a wide range of applications in the fields of text editing, bioinformatics, etc. For example, in text editing, it can be used to calculate the similarity of two documents; in bioinformatics, it can be used to analyze the similarity of gene sequences.
In the future, with the continuous growth of data scale and the improvement of efficiency requirements, we can further explore more optimized algorithms and data structures to solve more complex string processing problems. At the same time, the research on the longest common subsequence problem can also be extended to the case of multiple strings, as well as solutions under specific constraints. I hope this article can help readers better understand the longest common subsequence problem and flexibly use related algorithms in actual programming.
The above is personal experience. I hope you can give you a reference and I hope you can support me more.