Longest Common Subsequence
Align two strings with a DP table.
What a Subsequence Is
A subsequence keeps characters in order but may skip some. From 'abcde' you can take 'ace', but never 'aec'.
The LCS Goal
Given two strings, the longest common subsequence is the longest sequence that appears in both, in the same relative order.
All lessons in this course
- Path Counting on a Grid
- Minimum Path Sum with Obstacles
- Longest Common Subsequence
- Edit Distance Step by Step