Medium Problemsstringgrid

Wildcard Pattern Matching

Given a text string and a pattern that may contain '?' for any single character and '*' for any sequence of characters, including none, decide whether the pattern matches the entire text.

Do this lesson first: longest common subsequence

Example input

pattern = "a*b?c", text = "abycbxcbzc"

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. Here m = 5 is the pattern's length and n is how many letters of abycbxcbzca the slider takes, 10 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 2's gutter reads 2 * and column 4's reads 4 c. The answer is yes or no, so the page writes each cell as 1 or 0. It is a whole-prefix match, pinned at both ends, rather than "the pattern occurs somewhere in the text", and that is what lets a cell be built from smaller ones. Peel the last character off the pattern, and what remains has to account for every letter before the ones that character took, no more and no fewer. A somewhere-answer cannot promise that: b?c occurs in abycb, at letters 2 to 4, yet a*b?c does not match abycb, because the pattern has to end where the text does and nothing after its c can take the final b.

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) if p[i - 1] is *, else min(ok, dp[i - 1][j - 1]), where ok = 1 if p[i - 1] is ? or equals t[j - 1], else 0

Look at the pattern's last character, p[i - 1], and ask which text letters it takes. A letter or a ? takes exactly one, and because it is last, the one it takes is the text's last letter, t[j - 1]. That works if the two agree, which is what ok records (a ? agrees with any letter), and if the shorter prefixes, the pattern's first i - 1 characters and the text's first j - 1 letters, match entirely, which is the diagonal. Both have to hold. A star takes a run of letters at the end of the text, possibly an empty run. Either it matches nothing more, and the pattern's first i - 1 characters must match all j letters: the cell above, dp[i - 1][j]. Or it swallows at least one letter, and because the star is last, its run ends with t[j - 1]; set that letter aside, and the same star, still the pattern's last character, takes whatever is left of its run, possibly nothing. So the first i characters must match the first j - 1 letters: the cell to the left, dp[i][j - 1], in the SAME row, because swallowing a letter does not use the star up. That left cell has already weighed the star taking two, three or more letters, which is why two reads cover a run of any length. Either case is enough. On 1s and 0s, both-have-to-hold (AND) is the smaller of the two, min, and either-is-enough (OR) is the larger, max. The page writes them that way, so each computed cell's narration ends in a min or a max, and a star cell lists the cell above first and the cell to the 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, so a text with a letter in it is out of reach. Column 0 is the pattern against the empty text, and a star is the one character that can match nothing, so dp[i][0] = 1 exactly when the pattern's first i characters are all stars. That is a closed form of the pattern alone, not a recurrence, and the snippet writes it that way. On a*b?c rows 1 to 5 of column 0 are 0, row 2's a* included, because the a needs a letter. At the drive size that is 16 bases: 11 across row 0 for columns 0 to 10, and 5 more down column 0 for rows 1 to 5. A star cell reads the cell above and the cell to its left in its own row; a letter or ? cell reads the diagonal, up and to the left. A row-major sweep, left to right within each row, has finished each of those before it is needed, and the left-to-right part is what the star depends on: its left neighbour was written one step earlier in the same row.

Tabulation over all (m + 1) × (n + 1) cells, 66 at the drive size. A star cell reads its own row and the row above, and a letter or ? cell reads the row above, so two rolling rows of n + 1 cells are enough. Drag the slider and the text grows one letter at a time while the pattern stays put; the answer goes 1, 0, 0, 1, 0, 0, 1, 0 across lengths 4 to 11. The rhythm comes from the end of the pattern. After the star, b?c is three characters that take exactly one letter each, the ? included: it takes one letter, not none and not two. So the text has to end in b, any one letter, then c, and the star takes whatever sits between the opening a and that b. The text's c's are its letters 4, 7 and 10, each two letters after a b, so lengths 4, 7 and 10 match, with the star taking nothing, byc and bycbxc in turn. At lengths 5, 6, 8, 9 and 11 the text ends in b, x, b, z and a; the c row's ok is 0 at the last cell, and min(0, anything) is 0. In the table this is row 3's 1s, under the b's, moving one column right into row 4 and one more into row 5, where each lands on a c.

Time O(m × n)Space O(m × n), reducible to O(n) with two 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, so a text with a letter in it is out of reach. Column 0 is the pattern against the empty text, and a star is the one character that can match nothing, so dp[i][0] = 1 exactly when the pattern's first i characters are all stars. That is a closed form of the pattern alone, not a recurrence, and the snippet writes it that way. On a*b?c rows 1 to 5 of column 0 are 0, row 2's a* included, because the a needs a letter. At the drive size that is 16 bases: 11 across row 0 for columns 0 to 10, and 5 more down column 0 for rows 1 to 5. A star cell reads the cell above and the cell to its left in its own row; a letter or ? cell reads the diagonal, up and to the left. A row-major sweep, left to right within each row, has finished each of those before it is needed, and the left-to-right part is what the star depends on: its left neighbour was written one step earlier in the same row.

Rows ↓
Cols →

∅

1 a

2 b

3 y

4 c

5 b

6 x

7 c

8 b

9 z

10 c

∅

1

0

1 a

0

1

0

2 *

0

1

3 b

0

1

0

1

0

1

0

4 ?

0

1

0

1

0

1

0

5 c

0

1

0

1

0

1

Rows ↓pattern: a*b?c

Cols →text: the first n letters of abycbxcbzca

wildcard-pattern-matching.ts

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

Base caseComputedBeing readAnswer

The code, the trap, the variations

wildcard-pattern-matching.ts

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

Where people go wrong

Letting the star read the diagonal instead of its left neighbour: max(dp[i - 1][j], dp[i - 1][j - 1]). It looks like the letter and ? rows, which read the diagonal too, but the diagonal moves the pattern on past the star, so the star can take nothing or exactly one letter and is then spent; it has turned into a ? that may be skipped. On this input row 2 then holds 1 at columns 1 and 2 and 0 from column 3 on, where the correct row 2 is 1 at each column from 1 up. The slider gives 1, 0, 0, 0, 0, 0, 0, 0 instead of 1, 0, 0, 1, 0, 0, 1, 0: right at length 4, where the star takes nothing, and wrong at length 7 and at the drive size 10, where it has to take three letters and six. The left read stays in the star's own row so that the star can keep taking letters.

Add a + that matches one or more letters, and use it in place of the star: a+b?c.
The recurrence gains one rule, for a + row, and the letter, ? and * rules stay. A + cannot match nothing, so the cell above drops out. It takes the text's last letter either as the first letter of its run, which moves the pattern on past it and reads the diagonal, or as one more letter in a run already started, which keeps it in play and reads the cell to the left in its own row: dp[i][j] = max(dp[i - 1][j - 1], dp[i][j - 1]). A + is a ? followed by a *, and this is those two rows folded into one. Among the bases, row 0 stays as it is and column 0 keeps its closed form, all stars; a + is not a star, so a prefix that contains one gets 0. With a+b?c the slider gives 0, 0, 0, 1, 0, 0, 1, 0: length 4 drops to 0, because abyc matched a*b?c with the star taking nothing, and a + has to take at least one letter, which leaves b?c two letters for its three.
Match letters case-insensitively.
Only ok changes: compare p[i - 1] and t[j - 1] after lower-casing both, so A against a gives ok = 1. The star rule, the ? rule, the bases and the sweep stay as they are. This page's pattern and text are already lowercase, so its answers do not move. With the text in capitals, ABYCBXCBZCA, the case-sensitive table answers 0 at all eight lengths, since row 1's a meets an A in column 1 and fails, and the case-insensitive one gives back 1, 0, 0, 1, 0, 0, 1, 0.

Minimum insertions for palindrome Regular Expression Matching