Proficient Level
Implement the longestCommonSubsequenceLength method that returns the length of the longest common subsequence of two strings.
The input contains two strings, first and second. Your task is to return the length of their longest common subsequence.
A common subsequence is a sequence of characters that appears in both strings in the same order, but the characters do not need to be continuous. For example, for abcde and ace, the longest common subsequence is ace, so the answer is 3.
Example 1
Input
first (string) =
abcdesecond (string) =
aceReturns (int)
3Example 2
Input
first (string) =
abcsecond (string) =
abcReturns (int)
3Example 3
Input
first (string) =
abcsecond (string) =
defReturns (int)
0Use a two-dimensional dynamic programming table.
Let dp[i][j] store the longest common subsequence length using the first i characters of the first string and the first j characters of the second string.
If the current characters match, add 1 to the answer from the previous diagonal cell. If they do not match, take the better answer from removing one character from either string.
Pseudocode:
function longestCommonSubsequenceLength(first, second):
n = length(first)
m = length(second)
dp = 2D array of size (n + 1) x (m + 1) filled with 0
for i from 1 to n:
for j from 1 to m:
if first[i - 1] == second[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[n][m]Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run