Longest Common Subsequence
1/0
1.0x
Longest Common Subsequence
O(m * n)
Space: O(m * n)
Pseudocode
1
procedure LCS(X, Y)
2
m ← length(X), n ← length(Y)
3
create dp[0..m][0..n] = 0
4
for i ← 1 to m do
5
for j ← 1 to n do
6
if X[i-1] = Y[j-1] then
7
dp[i][j] ← dp[i-1][j-1] + 1
8
else
9
dp[i][j] ← max(dp[i-1][j], dp[i][j-1])
10
return dp[m][n]
Random Input