Blind 75 · #60 · 2-D Dynamic Programming

Longest Common Subsequence

Medium2-D dynamic programmingTime O(m · n)Space O(min(m, n)) with a rolling row

Longest Common Subsequence is a medium 2-D Dynamic Programming problem from the Blind 75. The key pattern is 2-d dynamic programming, and a good solution runs in O(m · n) time.

Problem

Return the length of the longest subsequence present in both strings.

Examples

Example 1

Input

["stone","longest"]

Output

Example 2

Input

["duelcoder","coder"]

Output

Example 3

Input

["kitten","sitting"]

Output

Approach

Compare prefixes: matching last characters extend the diagonal answer by one; otherwise take the better of dropping a character from either string.

Pattern	2-D dynamic programming
Time	O(m · n)
Space	O(min(m, n)) with a rolling row

Watch out for

A subsequence keeps order but not adjacency.

Longest Common Subsequence

Problem

Examples

Example 1

Example 2

Example 3

Approach

Watch out for

More 2-D Dynamic Programming problems