Longest Common Subsequence Length
Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
For example, "ace" is a subsequence of "abcde".
A common subsequence of two strings is a subsequence that is common to both strings.
Solution:
Test Input:
text1 = "abcde", text2 = "ace"Explanation:
There is no such common subsequence, so the result is 0.
Constraints:
1 <= text1.length, text2.length <= 1000
text1 and text2 consist of only lowercase English characters.
C++ [ Dynamic Programming ]
class Solution {
public:
// Function to find the length of the longest common subsequence in two strings.
int longestCommonSubsequence(string text1, string text2) {
int text1Length = text1.size(), text2Length = text2.size();
// Create a 2D array to store lengths of common subsequence at each index.
int dp[text1Length + 1][text2Length + 1];
// Initialize the 2D array with zero.
memset(dp, 0, sizeof dp);
// Loop through both strings and fill the dp array.
for (int i = 1; i <= text1Length; ++i) {
for (int j = 1; j <= text2Length; ++j) {
// If current characters match, add 1 to the length of the sequence
// until the previous character from both strings.
if (text1[i - 1] == text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
// If current characters do not match, take the maximum length
// achieved by either skipping the current character of text1 or text2.
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
}
}
}
// Return the value in the bottom-right cell which contains the
// length of the longest common subsequence for the entire strings.
return dp[text1Length][text2Length];
}
};