DP #16. Longest Common Subsequence. - mbhushan/dynpro GitHub Wiki

(15). Longest Common Subsequence.

Given two strings, find longest common subsequence between them.

String Y = abcdaf
String X = zbcdf
LCS = bcdf (len -> 4)

Formula:

if (X[i] == Y[j]) {
    T[i][j] = T[i-1][j-1] + 1;
} else {
    T[i][j] = Max(T[i-1][j], T[i][j-1])
}

	0	a	b	c	d	a	f
0	0	0	0	0	0	0	0
z	0	0	0	0	0	0	0
b	0	0	1	0	0	0	0
c	0	0	1	2	2	2	2
d	0	0	1	2	3	3	3
f	0	0	1	2	3	3	4

[Longest common subsequence] (https://github.com/mbhushan/dynpro/blob/master/DP_LongestCommonSubsequence/src/LongestCommonSubsequence.java)

• Time Complexity: O(n * m)
• Space Complexity: O(n * m)