Preparing for coding tests can be somewhat challenging, but systematically mastering algorithm problems can lead to good results.
In this course, we will cover the Longest Common Subsequence (LCS) problem.
This problem is an important algorithmic question that measures how much two subsequences overlap in strings or sequences.
Problem Definition
Given two strings, the problem is to find the length of the longest common subsequence of these two strings.
The two strings are as follows:
- String A: “ABCBDAB”
- String B: “BDCAB”
In this case, the longest common subsequence of strings A and B is “BDAB” or “BCAB”, and their length is 4.
To solve this problem, we will use a Dynamic Programming technique.
Problem Solving Strategy
The Longest Common Subsequence (LCS) problem can be solved using both recursive problem-solving approaches and dynamic programming.
The recursive approach is simple but has a very high time complexity, making it impractical. Therefore, we will use dynamic programming.
1. Understanding Dynamic Programming
Dynamic Programming (DP) is a method that divides problems into smaller subproblems and solves each subproblem just once, storing the results (caching).
We use a 2D dynamic array to solve the LCS problem. Each cell in the array stores the LCS length of the substring.
2. Constructing the DP Table
Let the lengths of strings A and B be m and n, respectively.
The DP table (longestCommonSubsequence array) is constructed with a size of (m + 1) x (n + 1).
Here, DP[i][j] represents the LCS length up to the first i characters of string A and the first j characters of string B.
3. Setting the Recurrence Relation
To fill the DP table, we use the following recurrence relations:
- If A[i-1] == B[j-1], then
DP[i][j] = DP[i-1][j-1] + 1 - Otherwise,
DP[i][j] = max(DP[i-1][j], DP[i][j-1])
This allows us to calculate the LCS of the two strings.
C++ Implementation
Now let’s implement the above theory in C++ code.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int calculateLCS(const string &A, const string &B) {
int m = A.length();
int n = B.length();
// Initialize the DP table
vector<vector<int>> DP(m + 1, vector<int>(n + 1, 0));
// Fill the DP table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (A[i - 1] == B[j - 1]) {
DP[i][j] = DP[i - 1][j - 1] + 1;
} else {
DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]);
}
}
}
return DP[m][n];
}
int main() {
string A = "ABCBDAB";
string B = "BDCAB";
int length = calculateLCS(A, B);
cout << "The length of the longest common subsequence is " << length << "." << endl;
return 0;
}
Code Explanation
In the above C++ code, the calculateLCS function is used to compute the LCS of the two strings.
First, the DP table is initialized, and then comparisons are made for each pair of characters while filling the DP table.
Finally, the length of the longest common subsequence is stored in the bottom right cell of the DP table (DP[m][n]).
Time Complexity
The time complexity of this algorithm is O(m * n), and the space complexity is also O(m * n).
This is proportional to the lengths of the two strings, so if the input string lengths are long, it may affect performance.
Conclusion
In this lecture, we covered the problem of finding the longest common subsequence between two strings.
We learned how to solve the problem using C++ and dynamic programming, and the longest common subsequence problem is one of the frequently encountered problems in coding tests.
If you practice and learn similar algorithms through various problems, you should be able to achieve good results in coding tests.
Thank you!