Wildcard / regex matching DP

44 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Does the pattern *a*b match the word adceb? Here ? stands for any one letter and * stands for any run of letters, including none. By hand you try: the first * takes nothing, a matches a, the second * takes dce, b matches b. Yes. Now try *a*b against adcebx: the b must be last but the word ends in x, so no.

The trouble with doing it by hand is the stars. Each * can take 0, 1, 2, ... letters, and with several stars the number of ways to split the word among them explodes. Guessing one split and backing up when it fails can take exponential time on nasty inputs like a*a*a*a*b against aaaaaaaaaaaaac.

Build the structure, one piece at a time

Piece one: a table of yes/no cells, one row per prefix of the word (including empty) and one column per prefix of the pattern. dp[i][j] means "the first i letters of the word match the first j characters of the pattern".

Piece two: the empty row. The empty word matches a pattern prefix only if that prefix is all stars, since each star can take nothing. So dp[0][0] = yes, and dp[0][j] = yes while pattern[j] is *.

Piece three: the inside, by the pattern character in column j:

1. a letter or ?: it must consume exactly the word's letter i, and the rest must match, so dp[i][j] = dp[i − 1][j − 1] and (letters equal or the character is ?);
2. a *: it takes nothing, so look left, dp[i][j − 1]; or it takes one more letter, so look up, dp[i − 1][j]. Either makes the cell yes.

That second rule is the whole idea: a star taking k letters is "a star taking k − 1 letters, then one more", so you never enumerate k.

Row a, column a: letters equal and the diagonal (ε, *) is ✓, so ✓. Row d, column second *: left is (d, a) = ·, up is (a, *) = ✓, so ✓. Bottom-right: b equals b and the diagonal (e, *) is ✓: match.

Why it is correct

The invariant: each filled cell correctly says whether its word prefix matches its pattern prefix. Empty row: proved above. Letter or ? column: the pattern character must consume exactly the word's last letter, so the two shorter prefixes must match, which is the diagonal. Star column: in any matching, the star consumed some number of trailing letters; if zero, the prefix without the star matches (left); if at least one, drop the last word letter and the same star still matches what remains (up). Both directions are exact, so the cell is right.

Why it is fast

work = (n + 1)(m + 1) cells × constant

A 2,000-letter word against a 2,000-character pattern is 4 million cells, while the back-up search can take time exponential in the number of stars.

How to recognise it in an interview

Cues: "wildcard", "? and *", "regular expression", "does the pattern cover the whole string", two strings where one contains special characters. The first thing to say: "a table over prefixes; a star looks left for zero letters or up for one more." Wildcard Matching is the example above. Regular Expression Matching is the harder sibling: there the star applies to the character before it, so the "one more" branch also checks that the word's letter matches that preceding character.

02The idea in one line

A star either matches nothing (drop it) or eats one more character.

Reach for it when: Regular expression matching, wildcard matching.

Cost: O(nm) time.

03The walk-through, step by step

The video works one example: Wildcard match 'adceb' vs '*a*b'. These are its captions in order, so you can follow without the video or check a step you missed.

1. '?' matches one char; '' matches nothing (look left) or one more char (look up)
2. Row ε: only a prefix of stars matches the empty string
3. Row 'a': star columns copy ← or ↑; letter columns need a match ↖
4. Row 'd': star columns copy ← or ↑; letter columns need a match ↖
5. Row 'c': star columns copy ← or ↑; letter columns need a match ↖
6. Row 'e': star columns copy ← or ↑; letter columns need a match ↖
7. Row 'b': star columns copy ← or ↑; letter columns need a match ↖
8. dp[5][4] is ✓: '' ate 'adc', 'e' went to the 2nd '', 'b' matched
9. |s| × |p| table, O(1) per cell: O(n·m)

04Asked at Google

2 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Dynamic Programming: 1-D linear DP, Kadane (best ending here), Longest increasing subsequence, Grid path DP, 0/1 knapsack (subset sum), Unbounded knapsack (coin change), Two-sequence DP (LCS / edit distance), Palindromes: expand or table, Prefix segmentation DP, Interval DP (last operation), State-machine DP (stocks), Bitmask DP over subsets, Memoised DFS (top-down), Digit DP, Game DP (minimax on a range), Counting ways with modulo, DP over sorted keys (chains).