codaBack to Academy
dynamic programming
Longest Common Subsequence
The Longest Common Subsequence (LCS) problem finds the longest subsequence common to two sequences. Unlike substrings, subsequences do not need to be contiguous. A 2D DP table is constructed where dp[i][j] represents the length of the LCS of the first i characters of string A and the first j characters of string B. If characters match, we extend the previous LCS; otherwise, we take the maximum of excluding one character from either string.
Use Cases
- •Diff tools for comparing files and version control systems
- •DNA and protein sequence alignment in bioinformatics
- •Spell checking and plagiarism detection in text analysis
Complexity Analysis
| Metric | Best | Average | Worst |
|---|---|---|---|
| Time | O(mn) | O(mn) | O(mn) |
| Space | O(mn) | ||
Visualization
| B | D | C | A | B | ||
|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | |
| A | 0 | 0 | 0 | 0 | 0 | 0 |
| B | 0 | 0 | 0 | 0 | 0 | 0 |
| C | 0 | 0 | 0 | 0 | 0 | 0 |
| B | 0 | 0 | 0 | 0 | 0 | 0 |
| D | 0 | 0 | 0 | 0 | 0 | 0 |
Implementation
Output
Click "Run Code" to see output...