Think about a search box that supports * for "anything" and ? for "any one character," the way old file explorers let you type report*.pdf to find every report. Making that actually work under the hood is dynamic programming (DP), and it's one of the places senior interviews specifically probe, because a wrong transition often looks right and only fails on tricky inputs. This lesson pushes DP past the "fill a 1D table" problems from earlier lessons into 2D string-matching DP, where the transition itself is the hard part. Interviewers use these problems to check whether you actually understand the state you're building, rather than having memorized a template.

Recognizing a 2-string matching DP

Regex matching, wildcard matching, and edit distance all share one shape: two strings (or a string and a pattern) being compared position by position. Once you can spot that shape, the setup is always the same three steps.

1. Define dp[i][j] as the answer for the first i characters of string s and the first j characters of the other string t.
2. Build a table sized (len(s)+1) x (len(t)+1). Row 0 and column 0 stand for the empty prefix, which kills most off-by-one bugs before they start.
3. Fill row by row, and each cell's answer depends only on (i-1, j), (i, j-1), and (i-1, j-1), the cells directly above, to the left, and diagonally above-left.

Reach for this shape whenever you see: two sequences being compared, transformed, or aligned (edit distance, longest common subsequence, interleaving strings); or * / ? wildcard-style matching against a pattern.

Remember: two strings being compared, one table with an extra empty-prefix row and column. That setup is the same for edit distance, wildcard matching, and regex matching.

State reduction

State reduction means shrinking dp[i][j][k]... down to the smallest set of indices that fully describes a subproblem. Every DP problem starts with too much information in your head: position in the string, position in the pattern, whether you're mid-star, how many stars used so far. The real skill is proving most of that is unnecessary.

For string matching problems, the state is almost always (i, j): "does s[:i] match p[:j]?" You don't need to track how it matched, only whether it did, because what happens next only depends on that yes/no plus the remaining suffixes. That's the reduction: from "the full matching history" down to "one bit per (i, j) pair."

Rule of thumb: if two different "histories" lead to the same future behavior, they belong in the same state. If your DP table has an extra dimension, ask whether that dimension actually changes what happens next.

Remember: don't track how you got here, only whether you're in a valid state now. If the future doesn't care about the history, the state shouldn't either.

Space optimization

Once you have a correct dp[i][j] table, look at the transition. If dp[i][j] only ever reads from row i-1 (and maybe row i), you don't need the full 2D table: two 1D rows (prev, curr) are enough, or even one row updated carefully in place.

This matters in interviews for two reasons. It shows you understand the dependency structure of your own recurrence, not just that you wrote one down. And it's a real production concern: a 10,000 x 10,000 DP table is 100 million cells; a rolling array is 10,000 cells.

Pitfall: when you roll the array, any base-case reset (dp[i][0]) has to happen explicitly inside the loop, since you're reusing the same memory. Forgetting this is the number one bug in rolling-array code.

Remember: if a cell only ever reads the row above it, you don't need the whole table, just that one row. Mention the shrink out loud even if you don't have time to code it.

Complex transitions

The wildcard and regex family have "look-behind" transitions. p[j-1] == '*' involves more than comparing one pair of characters: it branches into "match zero of the preceding element" versus "match one more of the current string," and both branches have to be OR'd together. This is the part candidates get wrong under pressure: they handle the plain character-match case fine, then panic on * and either miss a branch or mix up i and j.

The reliable process: say the recurrence out loud in plain English first ("if the pattern character is *, either the string character is unused entirely, since * matched zero times, or the string character is consumed and we stay on the same pattern position, since * can match more"), then transcribe it directly into code. Don't try to write the branch logic without saying it out loud first.

Remember: never code a * transition cold. Say the two branches in plain English first, then translate the sentence into code.

Regular Expression Matching

LeetCode 10 · Regular Expression Matching · DP · Hard

Intuition: . matches any single character; * matches zero or more of the preceding element (not the literal character before *, but that pattern unit). Because * looks back one pattern character, dp[i][j] has to consider p[j-2] whenever p[j-1] == '*'.

Approach: Build dp[i][j] = "does s[:i] match p[:j]?" Base case: an empty pattern only matches an empty string, but patterns like a*, a*b* can also match an empty string, so dp[0][j] needs its own rule. For each cell, branch on whether the current pattern character is *.

Complexity: O(mn) time, O(mn) space (rollable to O(n), see Space optimization above).

Common mistakes: forgetting the dp[0][j] base case for patterns that can match an empty string; indexing p[j-2] when j < 2 (safe here because a valid regex never starts with *, but always double-check input assumptions in an interview); confusing "zero occurrences" (dp[i][j-2]) with "one occurrence" (dp[i-1][j]), when both actually need to be considered together.

Remember: * in regex looks backward at the pattern character before it. Both "use it zero times" and "use it one more time" have to be checked.

Wildcard Matching

LeetCode 44 · Wildcard Matching · DP · Hard

Intuition: ? matches exactly one character, * matches any sequence, including empty, of characters. This is simpler than regex, because * doesn't look back at a preceding element here: it's a free-standing wildcard.

Approach: dp[i][j] = "does s[:i] match p[:j]?" When p[j-1] == '*', it can either match zero characters of s (dp[i][j-1]) or consume one more character of s and stay matched against the same * (dp[i-1][j]). This is the O(m*n) time, O(n) space version.

Complexity: O(m*n) time, O(n) space.

Common mistakes: mixing up this *'s "zero or more characters" meaning with regex's "zero or more of the preceding element" from the problem above. They look similar, but the transition differs, since wildcard's * never looks back. Also, forgetting to reset curr[0] = False each row when rolling the array; and assuming consecutive * characters need special handling, when the DP already collapses them to the same matching power as one *, with no pre-processing needed.

Remember: wildcard's * never looks back at a specific character, it's just "any sequence." That's the one difference from regex's * to keep straight.

Minimum Path Sum

LeetCode 64 · Minimum Path Sum · DP · 2D

Intuition: Only two moves are allowed, right or down, so the minimum cost to reach (i, j) is that cell's own cost plus the cheaper of "coming from above" or "coming from the left."

Approach: In-place DP directly on the input grid skips extra space entirely. It's the state-reduction idea applied aggressively: you don't even need a separate table, because each cell's dependency (up, left) is already computed and won't be needed again.

Complexity: O(m*n) time, O(1) extra space (mutates the input in place, so mention that trade-off out loud in an interview, since it isn't always acceptable).

Common mistakes: forgetting the first row/column special cases; they only have one possible direction of approach, not two. Also, mutating the grid when the interviewer expects the input preserved: ask first, or copy the grid if unsure.

Remember: the first row and column only have one way in. Everywhere else, take the cheaper of "from above" or "from the left."

Longest Palindromic Substring

LeetCode 5 · Longest Palindromic Substring · DP

Intuition: A substring s[i:j] is a palindrome if s[i] == s[j-1] and the inner substring s[i+1:j-1] is also a palindrome. That's a valid DP, but the expand-around-center technique gets the same O(n²) time with O(1) space, and it's the version to lead with in an interview.

Approach (expand around center): Every palindrome has a center, either a single character (odd length) or a gap between two characters (even length). Try all 2n - 1 centers and expand outward while characters keep matching.

Complexity: O(n²) time, O(1) space. The classic DP table version is O(n²) time and O(n²) space, worth knowing both so you can explain the trade-off if asked.

Common mistakes: forgetting the even-length center case (a gap, not a character), which silently misses palindromes like "abba". Also, an off-by-one in the return of expand: the loop exits one step past the actual palindrome boundary, so you must correct by 1 in each direction.

Remember: every palindrome has a center, either on a character or in the gap between two. Check both kinds of center at every position.

The two * semantics in this lesson are easy to blur together once you've seen both: regex's * looks back at the preceding pattern element, wildcard's * is free-standing and never looks back. If you catch yourself writing the same transition for both problems, stop and re-derive it from the plain-English description first.