Proficient Level
Implement the longestCommonSubsequenceDpLength method that returns the LCS length using dynamic programming.
The input contains two strings: first and second. Your task is to return the length of their longest common subsequence.
A subsequence keeps characters in the same relative order but does not need to use consecutive characters. The same subsequence must appear in both strings.
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 dynamic programming to compare prefixes of both strings.
Let dp[i][j] represent the LCS length using the first i characters of first and the first j characters of second.
If the current characters match, extend the previous diagonal answer by one. If they do not match, take the better result from skipping one character from either string.
Pseudocode:
function longestCommonSubsequenceDpLength(first, second):
m = length(first)
n = length(second)
dp = 2D array of size (m + 1) x (n + 1) filled with 0
for i from 1 to m:
for j from 1 to n:
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[m][n]Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run