Deviopath › Python

Longest Common Subsequence

Hard · Algorithms

A subsequence keeps characters in order but may skip some: "ace" is a subsequence of "abcde". The longest common subsequence (LCS) of two strings is the longest string that is a subsequence of both. Diff tools are built on this idea.

Dynamic programming: let dp[i][j] be the LCS length of a[:i] and b[:j]. If a[i-1] == b[j-1], then dp[i][j] = dp[i-1][j-1] + 1; otherwise it is max(dp[i-1][j], dp[i][j-1]).

Write lcs_length(a, b) that returns the length of the LCS. Strings have up to 1000 characters each, so an O(len(a) * len(b)) table is fine.

Next: 0/1 Knapsack