Regex

String DP Patterns — Edit Distance, LCS, Interleaving, and Regex Matching

The four canonical string DP problems — edit distance, longest common subsequence, interleaving strings, and regular expression matching — share a common 2D state structure. Master the family and you cover 80 percent of FAANG string DP questions.