DP #03. Longest Common Subsequence. - mbhushan/dynpro GitHub Wiki
(3). Longest Common Subsequence.
Given two strings A & B, find longest common subsequence between them.
Examples:
LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3.
LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4.
| 0 | A | G | G | T | A | B | |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| G | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| X | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| T | 0 | 0 | 1 | 1 | 2 | 2 | 2 |
| X | 0 | 0 | 1 | 1 | 2 | 2 | 2 |
| A | 0 | 1 | 1 | 1 | 2 | 3 | 3 |
| Y | 0 | 1 | 1 | 1 | 2 | 3 | 3 |
| B | 0 | 1 | 1 | 1 | 2 | 3 | 4 |
Formula:
if (S1[i] == S2[j]) {
T[i][j] = T[i-1][j-1] + 1;
} else {
T[i][j] = Max (T[i-1][j], T[i][j-1]);
}
- Time Complexity: O(n*m)
- Space Complexity:O(n*m)