The problem
Implement pattern matching where . matches any single letter and x* matches zero or more copies of the letter x. The pattern must match the whole text.
Input: text = "aab", pattern = "c*a*b" Output: true (c* = nothing, a* = "aa", b = "b")
Picture it
Picture a stencil with wildcards laid over the text. The table cell (i, j) asks: does the first j characters of the pattern match the first i letters of the text? A star pair “x*” can be used zero times (skip it in the pattern) or once more (if the text letter matches x, stay on the same pattern pair and eat one letter).
How to recognise it
- You match a pattern against a text, and the pattern has operators with several possible meanings.
- A star
x*gives a choice at every step: use it zero times, or one more time. - After each decision, what is left is again a prefix of the pattern against a prefix of the text.
- The whole text must match the whole pattern, so only the final cell matters.
- Sizes are tiny (20 each), a hint that something exponential is waiting to be tamed.
Start with brute force
Look at the first pattern letter. If it is followed by a star, either skip the pair or eat one matching letter and stay on the same pair. Otherwise the first letters must match and both move on.
def match_brute(s, p):
if not p:
return not s
first = bool(s) and p[0] in (s[0], ".")
if len(p) >= 2 and p[1] == "*":
return match_brute(s, p[2:]) or (first and match_brute(s[1:], p))
return first and match_brute(s[1:], p[1:])
Several stars in a row make the recursion explode. For text "a" * 20 against the pattern "a*" * 10 + "b" it makes about 74 million calls, then answers False. Time is exponential in the worst case; space is O(m + n) for the recursion plus the string slices.
From brute force to the idea
- Find the waste. Each call is described by a pair (suffix of text, suffix of pattern), and there are only (m + 1)(n + 1) of them. The same pair is reached through many different star choices.
- Define the table.
ok[i][j]is True if the first j characters of the pattern match the first i characters of the text.ok[0][0]is True. - Plain letter or dot at
p[j-1]: it must match the last text letter, sook[i][j] = ok[i-1][j-1], and only wheni > 0andp[j-1]is that letter or a dot. - A star at
p[j-1]means the pairx*is the last two characters. Zero uses: drop the pair,ok[i][j-2]. One more use: the text letters[i-1]must matchx(orxis a dot), and the text without it must already match the same pattern,ok[i-1][j]. Staying onjis what allows any number of copies. - Fill the rows in order, starting at row 0 (empty text), because patterns like
a*b*can match the empty text. The answer isok[m][n].
This is the key idea: the star never loops forever, because "one more copy" shrinks the text and "zero copies" shrinks the pattern.
The key idea
dp over (text prefix, pattern prefix); handle “*” as zero uses (j − 2) or one more use (i − 1). O(m × n).
Python solution
def is_match(s, p):
m, n = len(s), len(p)
ok = [[False] * (n + 1) for _ in range(m + 1)]
ok[0][0] = True
for i in range(m + 1):
for j in range(1, n + 1):
if p[j - 1] == "*": # x* : zero copies, or one more
ok[i][j] = ok[i][j - 2] or (i > 0 and p[j - 2] in (s[i - 1], ".") and ok[i - 1][j])
elif i > 0 and p[j - 1] in (s[i - 1], "."):
ok[i][j] = ok[i - 1][j - 1]
return ok[m][n]In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | Exponential in the worst case: stars give two branches per step | O(m + n) depth, plus copies of the sliced strings |
| DP table (shown code) | O(m · n): each cell is a constant number of lookups | O(m · n): the whole table |
Edge cases
- Empty text and empty pattern: True.
- Empty text with stars (
"" , "a*b*c*"): True, because every pair can be used zero times. This is why row 0 must be filled. - Empty text, a dot (
"","."): False. A dot needs exactly one letter. .*matches anything, including the empty text and"ab".- Whole text needed:
("ab", "a*")is False and("aa", "a")is False, because leftover text is not allowed. - Zero copies (
("b", "a*b")): True.("aab", "c*a*b")is True too. - Invalid patterns: the code assumes every
*follows a letter or a dot, as the problem promises. A pattern starting with*is not checked.
Common mistakes
- Starting the outer loop at row 1, which loses the cases where the empty text matches (and therefore many later cells).
- Treating
x*as "one or more" and forgetting the zero-copy case. - Returning true as soon as the text is used up, even if pattern characters remain.
The pattern now uses ? (any single letter) and * (any sequence of letters, including none), with no letter in front of the star. For ("adceb", "*a*b") the answer is True and for ("acdcb", "a*c?b") it is False. Describe your approach, then write it if you like.
Compare with our answer
The same table works, but the star is simpler: it stands alone, so it can match zero letters (look left, ok[i][j-1]) or one more letter (look up, ok[i-1][j]). A leading star can match the empty text, so fill row 0 for stars.
def wildcard(s, p):
m, n = len(s), len(p)
ok = [[False] * (n + 1) for _ in range(m + 1)]
ok[0][0] = True
for j in range(1, n + 1):
if p[j - 1] == "*":
ok[0][j] = ok[0][j - 1]
for i in range(1, m + 1):
for j in range(1, n + 1):
if p[j - 1] == "*":
ok[i][j] = ok[i][j - 1] or ok[i - 1][j]
elif p[j - 1] in (s[i - 1], "?"):
ok[i][j] = ok[i - 1][j - 1]
return ok[m][n]
It gives False for ("aa", "a"), True for ("aa", "*"), False for ("cb", "?a"), and True for ("", "*"). Time and space O(m · n).
A strong answer mentions: the star as a free-standing wildcard, filling row 0 for leading stars, and the same (m + 1)(n + 1) table.
1. You must decide whether a pattern with * (zero or more of the previous letter) and . matches an entire text. Which approach fits best?
A star can match any number of letters, and a greedy star can eat letters that a later part of the pattern needs (as in "aaa" against "a*a"). The table keeps both choices.
2. In the star case, why is the second option ok[i - 1][j] and not ok[i - 1][j - 2]?
ok[i-1][j] means "the text without its last letter already matches the same pattern, star included", so more copies are still possible. Using j - 2 would allow exactly one copy.
3. A learner changes for i in range(m + 1) to for i in range(1, m + 1). Which call now returns a wrong answer?
Row 0 is never filled, so the zero-copy star pairs at the start (c*, a*) cannot match the empty text. Of these four calls only "aab" against "c*a*b" changes (to False); the others keep their correct result.
Score 60% or more and the lesson is marked complete.