Medium Problemsstringgrid

Regular Expression Matching

Given a text string and a pattern containing '.' for any single character and '*' meaning zero or more of the character right before it, decide whether the pattern matches the entire text.

Do this lesson first: longest common subsequence

Example input

pattern = "c*a*b.*c", text = "aabxbcyc"

Expected output

1 (the pattern matches)

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i][j] is 1 if the first i characters of the pattern p match the first j letters of the text t entirely, both prefixes used up, and 0 if not: the same yes-or-no state as wildcard pattern matching, written as 1 or 0 so that both-must-hold is a min and either-will-do is a max. Here m = 8 is the pattern's length and n is how many letters of aabxbcycd the slider takes, 8 at the drive size. Row i's own character is p[i - 1] and column j's letter is t[j - 1], which is why row 4's gutter reads 4 * and column 6's reads 6 c. The twist is that * has no meaning of its own. It belongs to the character in front of it, and the unit the pattern is made of is x*, zero or more copies of x. So c*a*b.*c is five units, c*, a*, b, .* and c, over eight rows, and a row that ends on a letter whose star sits on the next row, such as row 3, c*a, is an honest state of its own: a pattern whose a has not got its star yet. As in wildcard matching, the match is pinned at both ends rather than found somewhere. The text's first 7 letters, aabxbcy, contain a match of the whole pattern, aabxbc, and still dp[8][7] = 0, because the y is left over and no unit takes it. Being pinned is what lets a cell lean on smaller ones: peel the last unit off the pattern, and what remains has to account for exactly the letters in front of the ones that unit took.

dp[i][j] = max(dp[i - 2][j], min(fits(p[i - 2], t[j - 1]), dp[i][j - 1])) if p[i - 1] is *, else min(fits(p[i - 1], t[j - 1]), dp[i - 1][j - 1]), where fits(x, y) = 1 if x is . or equals y, else 0

Look at the pattern's last unit and ask which text letters it takes. If p[i - 1] is a letter or a ., the unit is that one character, and it takes exactly one letter, the text's last, t[j - 1]. That works if the two fit, which is what fits records (a . fits any letter), and if the shorter prefixes, the first i - 1 characters and the first j - 1 letters, match entirely, which is the diagonal. Both have to hold: min(fits, dp[i - 1][j - 1]). If p[i - 1] is a *, the unit is x*, two characters, with x = p[i - 2], and one of two things happens. Either it matches zero copies of x, so the whole unit drops out, letter and star together, and the first i - 2 characters must match all j letters: the cell TWO rows up, dp[i - 2][j]. Or it takes t[j - 1] as one more copy of x, which needs t[j - 1] to fit x, and stays available for any copies in front of that one, so the first i characters, star included, must match the first j - 1 letters: the cell to the left in the SAME row, dp[i][j - 1]. Either is enough, so the cell is the max of the two, and the second is itself a min, fits(x, t[j - 1]) against the left cell. This is where it parts from wildcard matching. Wildcard's * stands alone and takes any letters, so stopping it drops one character and reads ONE row up, and swallowing a letter needs no check. Here the * is the back half of x*, so dropping it drops its letter too and reads TWO rows up, and taking another letter has to check that letter against x. A star cell lists the cell two rows up first and the cell to its left second, in its gates and compare labels too.

Row 0 and column 0 are given rather than computed. dp[0][0] = 1: the empty pattern matches the empty text. dp[0][j] = 0 for j from 1 up: the empty pattern takes no letters. Column 0 is the pattern against the empty text, and an x* unit is the one thing that can match nothing, so dp[i][0] = 1 exactly when the first i characters cut into x* units throughout: i is even and the 2nd, 4th and every later even-position character up to i is a *. That is a closed form of the pattern alone, and the snippet writes it that way. On c*a*b.*c it is 1 at rows 2 and 4 (c* and c*a*) and 0 at rows 1, 3, 5, 6, 7 and 8: rows 1 and 3 end on a letter whose star is not in the prefix yet, and from row 5 down the bare b needs a letter. At the drive size that is 17 bases: 9 across row 0 for columns 0 to 8, and 8 more down column 0. A star cell reads two rows up and to its left in its own row; a letter or . cell reads the diagonal. A row-major sweep, left to right within each row, has written each of those before it is needed. The two-row jump has a consequence you can see in the table: rows 1, 3 and 6, the c, the a and the . that a star follows, are filled like the rest, yet no later cell reads any of them. The star row below each one jumps over it to the row above, and checks its letter against the text directly rather than through a cell. Their 1s, such as dp[3][1] (c*a matches a), are true and go unused; taking exactly one copy of x is covered by the star row instead, through its left read.

Tabulation over all (m + 1) × (n + 1) cells, 81 at the drive size and 90 at the top of the slider, the most a page here may draw. A star cell reads two rows up, so rolling rows need three rows of n + 1 cells, the current one and the two above it, one more than wildcard matching needs. Drag the slider and the text grows one letter at a time while the pattern stays put; the answer goes 0, 0, 1, 0, 1, 0 across lengths 4 to 9. The pattern ends in a bare c, which has to take the text's last letter, and in front of it .* takes anything at all. Before that, c*, a* and b take the text's opening aab, with c* taking nothing. So at each length on the slider the text matches exactly when its last letter is a c. Its c's are letters 6 and 8, so lengths 6 and 8 match, and lengths 4, 5, 7 and 9 end in x, b, y and d. In the table this is row 7, .*, holding 1 at each column from 3 on, and row 8 keeping a 1 only under a c.

Time O(m × n)Space O(m × n), reducible to O(n) with three rolling rows

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

Row 0 and column 0 are given rather than computed. dp[0][0] = 1: the empty pattern matches the empty text. dp[0][j] = 0 for j from 1 up: the empty pattern takes no letters. Column 0 is the pattern against the empty text, and an x* unit is the one thing that can match nothing, so dp[i][0] = 1 exactly when the first i characters cut into x* units throughout: i is even and the 2nd, 4th and every later even-position character up to i is a *. That is a closed form of the pattern alone, and the snippet writes it that way. On c*a*b.*c it is 1 at rows 2 and 4 (c* and c*a*) and 0 at rows 1, 3, 5, 6, 7 and 8: rows 1 and 3 end on a letter whose star is not in the prefix yet, and from row 5 down the bare b needs a letter. At the drive size that is 17 bases: 9 across row 0 for columns 0 to 8, and 8 more down column 0. A star cell reads two rows up and to its left in its own row; a letter or . cell reads the diagonal. A row-major sweep, left to right within each row, has written each of those before it is needed. The two-row jump has a consequence you can see in the table: rows 1, 3 and 6, the c, the a and the . that a star follows, are filled like the rest, yet no later cell reads any of them. The star row below each one jumps over it to the row above, and checks its letter against the text directly rather than through a cell. Their 1s, such as dp[3][1] (c*a matches a), are true and go unused; taking exactly one copy of x is covered by the star row instead, through its left read.

Rows ↓
Cols →

∅

1 a

2 a

3 b

4 x

5 b

6 c

7 y

8 c

∅

1

0

1 c

0

2 *

1

0

3 a

0

1

0

4 *

1

0

5 b

0

1

0

6 .

0

1

0

7 *

0

1

8 c

0

1

0

1

Rows ↓pattern: c*a*b.*c

Cols →text: the first n letters of aabxbcycd

regular-expression-matching.ts

1function isMatch(p, t) {
2 const m = p.length, n = t.length;
3 const fits = (x, y) => (x === "." || x === y ? 1 : 0);
4 const unitsOfStars = (i) => i % 2 === 0 && [...p.slice(0, i)].every((c, k) => k % 2 === 0 || c === "*");
5 const dp = Array.from({ length: m + 1 }, (_, i) =>
6 Array.from({ length: n + 1 }, (_, j) => (j === 0 && unitsOfStars(i) ? 1 : 0)));
7 for (let i = 1; i <= m; i++) {
8 for (let j = 1; j <= n; j++) {
9 dp[i][j] = p[i - 1] === "*"
10 ? Math.max(dp[i - 2][j], Math.min(fits(p[i - 2], t[j - 1]), dp[i][j - 1]))
11 : Math.min(fits(p[i - 1], t[j - 1]), dp[i - 1][j - 1]);
12 }
13 }
14 return dp[m][n];
15}

Base caseComputedBeing readAnswer

The code, the trap, the variations

regular-expression-matching.ts

1function isMatch(p, t) {
2 const m = p.length, n = t.length;
3 const fits = (x, y) => (x === "." || x === y ? 1 : 0);
4 const unitsOfStars = (i) => i % 2 === 0 && [...p.slice(0, i)].every((c, k) => k % 2 === 0 || c === "*");
5 const dp = Array.from({ length: m + 1 }, (_, i) =>
6 Array.from({ length: n + 1 }, (_, j) => (j === 0 && unitsOfStars(i) ? 1 : 0)));
7 for (let i = 1; i <= m; i++) {
8 for (let j = 1; j <= n; j++) {
9 dp[i][j] = p[i - 1] === "*"
10 ? Math.max(dp[i - 2][j], Math.min(fits(p[i - 2], t[j - 1]), dp[i][j - 1]))
11 : Math.min(fits(p[i - 1], t[j - 1]), dp[i - 1][j - 1]);
12 }
13 }
14 return dp[m][n];
15}

Where people go wrong

Treating this * like wildcard matching's: stopping the star reads dp[i - 1][j], one row up, and column 0 is 1 only under a run of stars. Row i - 1 ends on the starred letter x itself, so zero copies has quietly become exactly one, and with the left read adding more, every x* now means one or more copies. On this input the pattern turns into c+a+b.+c, which needs the text to open with a c; this one opens with a, so at the drive size every cell below row 0 is 0, and the slider gives 0 at all six lengths where the right answers are 0, 0, 1, 0, 1, 0. Half the mistake can hide. Keep column 0's correct closed form and change only the star's upward read, and at the drive size it changes one cell, dp[7][3] (.* taking nothing after aab), from 1 to 0, and no answer on the slider moves. Dropping a star means dropping its letter with it, which is why the read goes two rows up.

Add a + meaning one or more copies of the character in front of it, and use it in place of a star.
A + row gets its own rule, and the letter, . and * rules stay. x+ is x followed by x*, and the bare x's row just above already says x was taken once, so the + row reads ONE row up for no more copies and keeps the star's left read for one more: dp[i][j] = max(dp[i - 1][j], min(fits(x, t[j - 1]), dp[i][j - 1])). That is the pitfall's formula, right this time, and it means the bare letter's row is read after all. Row 0 stays as it is; column 0 keeps its closed form with only * counted, so a prefix holding an x+ gets 0, since x+ needs a letter. Put c+ in front, c+a*b.*c, and the slider gives 0 at all six lengths, because the text opens with a, not c. Put a+ in place of a*, c*a+b.*c, and it stays 0, 0, 1, 0, 1, 0: in both matches on the slider a* takes two copies, aa, so asking for at least one changes nothing.
Add a ? meaning zero or one copy of the character in front of it (the regular-expression ?, not wildcard matching's any-one-letter ?), and use it in place of a star.
A ? row gets its own rule, and the letter, . and * rules stay. It reads two rows up for both of its cases and loses the left read, because x? cannot repeat. Zero copies is dp[i - 2][j], as for a star. One copy takes t[j - 1] and spends the unit, which is the diagonal two rows up: dp[i][j] = max(dp[i - 2][j], min(fits(x, t[j - 1]), dp[i - 2][j - 1])). Row 0 stays; column 0 counts a ? like a *, since x? can match nothing, so dp[i][0] = 1 when i is even and each even-position character is a * or a ?. With c*a?b.*c the slider gives 0 at all six lengths, because a? takes at most one a and the text opens with two. With c?a*b.*c it stays 0, 0, 1, 0, 1, 0, since c* took no c's in either match.

Wildcard Pattern Matching Arrange Balls with adjacent of different types