Coding · Dynamic programming
Wildcard pattern matching with ? and *
- Reported once
- Hard
- SDE intern (off-campus)
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
Given a text and a pattern, decide whether the pattern matches the entire text. In the pattern, ? stands for exactly one character, * stands for any run of characters including the empty run, and every other character matches only itself. For example, the text adceb matches the pattern *a*b, while the text acdcb does not match a*c?b. Both strings can be a few thousand characters long. A candidate report lists it among the problems of a long online coding round for an intern role.
Restated in our own words, not a quote from CRED or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
Before coding I would pin down the contract. Does ? match exactly one character and * any run including the empty run, as in shell globbing? Is the match against the whole text, not a substring? Can either string be empty, and are the characters limited to lowercase letters or can they be anything? Is there an escape for a literal ? or *, and how long can the strings get?
The report gives only the title, so I solve the standard contract: the whole text must match, ? is one character, * is zero or more characters, there are no escapes, comparison is case sensitive, and both strings may be empty and a few thousand characters long.
Brute force
Say the obvious answer and why it is too slow.
The direct approach is recursion on two positions, i in the text and j in the pattern. An ordinary pattern character or ? must match the text character at i, and then both positions advance. A * can swallow any number of characters, so the recursion tries every length: swallow nothing, one character, two, and so on up to the end of the text.
Without memory this is exponential. Each star multiplies the work by the number of positions it can take, so a pattern with k stars costs about O(n^k) calls on a text of length n, and a text of 2,000 letters against *a*a*a*a*b is hopeless. The recursion also solves the same pair (i, j) many times over, which is the sign that a table will fix it.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n^k) for a pattern with k stars, exponential in general
- Time
- O(n * m) for text length n and pattern length m
- Space
- O(m) using two rows
The pattern is dynamic programming over prefixes. Let dp[i][j] be true when the first i characters of the text are matched exactly by the first j characters of the pattern. The answer is dp[n][m], and every cell depends only on cells with smaller indices.
The base row is dp[0][0] = true, and dp[0][j] is true only while the pattern prefix is all stars, because only a star can match the empty text. For i above 0, dp[i][0] is false, since an empty pattern matches only an empty text. For an ordinary character or ?, dp[i][j] is true when dp[i-1][j-1] is true and the pattern character is ? or equals text[i-1]. For a star there are two ways to be right: the star matches nothing, so dp[i][j-1] must hold, or the star swallows text[i-1] and stays available for more, so dp[i-1][j] must hold. Either one is enough.
The second star rule is the whole trick. It never loops over run lengths: dp[i-1][j] already says that the star has matched some run ending at i-1, and extending that run by one character costs one step. That turns the exponential search into n times m cell updates.
Row i reads only row i-1 and earlier cells of its own row, so two rows are enough and the space drops to O(m). Out loud: "prefix table, a star is either empty or eats one more character, keep two rows."
Walk it through
A dry run on the example, step by step.
| Text read | Row for j = 0 to 4 | Last cell |
|---|---|---|
| (nothing yet) | TTFFF | F |
| a | FTTTF | F |
| ad | FTFTF | F |
| adc | FTFTF | F |
| adce | FTFTF | F |
| adceb | FTFTT | T |
Take the text adceb and the pattern *a*b. The columns of each row are the pattern prefixes of length 0 to 4: empty, *, *a, *a*, *a*b. Row 0 is TTFFF because the empty text matches the empty pattern and the pattern *, and nothing longer.
After reading a, the star can swallow it (column 1) and *a matches it (column 2), and the second star can then match nothing (column 3), giving FTTTF. Reading d turns column 2 off, since a does not match d, but column 3 stays on because the second star swallows d. The rows for c and e look the same for the same reason. The last character b is matched by the final b of the pattern, and column 3 of the previous row was true, so the last cell is true and the whole text matches.
The code
Runnable JavaScript, checked against test cases.
function isMatch(text, pattern) {
const n = pattern.length;
let row = new Array(n + 1).fill(false);
row[0] = true;
for (let j = 1; j <= n; j++) row[j] = row[j - 1] && pattern[j - 1] === "*";
for (let i = 1; i <= text.length; i++) {
const next = new Array(n + 1).fill(false);
for (let j = 1; j <= n; j++) {
const p = pattern[j - 1];
if (p === "*") next[j] = next[j - 1] || row[j];
else next[j] = row[j - 1] && (p === "?" || p === text[i - 1]);
}
row = next;
}
return row[n];
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
An empty text matches only a pattern made of stars, including the empty pattern, and the base row handles that. An empty pattern with a non-empty text is false, because the first cell of every later row is false. Runs of consecutive stars behave like one star, since the second star can always match nothing.
- Text longer than the pattern, no star: the table ends false, with no special case.
- ? against the empty text: false, because it needs one character.
- Star at either end: works through the empty-match rule and the swallow rule.
- Case: comparison is by exact character, so a and A differ.
- Special-looking characters: only ? and * in the pattern are wildcards, and in the text they are ordinary characters.
Follow-ups to expect
Where the interviewer pushes next.
- Can you do it in constant extra space, and what is the worst-case time of that version?
- How does this differ from regular expression matching, where a star repeats the previous element?
- How would you report which part of the text each star consumed?
- How would you match one pattern against millions of short texts?
- What changes if the pattern may contain an escape character for a literal ? or *?
Where candidates slip
The mistakes this problem punishes.
The commonest slip is the base row: setting dp[0][j] false for every j, which breaks patterns that start with a star and the empty text against *. The next is treating * like a regular expression star that repeats the previous character; here it stands alone and matches any characters.
Others: leaving out the empty-match rule dp[i][j-1], which fails a*b against ab; confusing dp[i-1][j] (the star swallows a character) with dp[i-1][j-1] (a one-to-one match); forgetting that the first cell of every row below row 0 must be false when rows are rolled, so a reused array leaks a stale true; matching a prefix of the text instead of all of it; and writing the plain recursion without a table, which times out on a few stars.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.