LCS and String DP (2D)

A 2D grid comparing prefixes of two strings: match → dp[i-1][j-1] + 1, mismatch → the best of skipping a character from either string.

Sub-patterns

• A — Longest Common Subsequence. The base 2D-string-DP shape.
• B — Edit Distance. Insert/delete/replace operations to transform one string into another.
• C — Distinct Subsequences. Count ways one string appears as a subsequence of another.
• D — String Interleaving. Can two strings interleave to form a third?
• E — Palindromic Substring/Subsequence. Longest palindrome as a contiguous substring or as a subsequence.

Practice set (9)

• Medium — Longest Common Subsequence, Edit Distance, Delete Operation for Two Strings, Longest Palindromic Substring, Longest Palindromic Subsequence, Interleaving String
• Hard — Distinct Subsequences, Wildcard Matching, Regular Expression Matching