LeetCode 10 · 2-D DP

Regular Expression Matching, explained with a picture

A stencil with wildcards and repeats.

Hard2-D DP
▶ Watch it step by step

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

  1. 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.
  2. 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.
  3. Plain letter or dot at p[j-1]: it must match the last text letter, so ok[i][j] = ok[i-1][j-1], and only when i > 0 and p[j-1] is that letter or a dot.
  4. A star at p[j-1] means the pair x* is the last two characters. Zero uses: drop the pair, ok[i][j-2]. One more use: the text letter s[i-1] must match x (or x is a dot), and the text without it must already match the same pattern, ok[i-1][j]. Staying on j is what allows any number of copies.
  5. Fill the rows in order, starting at row 0 (empty text), because patterns like a*b* can match the empty text. The answer is ok[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

ApproachTimeSpace
Brute forceExponential in the worst case: stars give two branches per stepO(m + n) depth, plus copies of the sliced strings
DP table (shown code)O(m · n): each cell is a constant number of lookupsO(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.
Your turn: wildcard matching

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.

Check what stuck

1. You must decide whether a pattern with * (zero or more of the previous letter) and . matches an entire text. Which approach fits best?

2. In the star case, why is the second option ok[i - 1][j] and not ok[i - 1][j - 2]?

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?

Score 60% or more and the lesson is marked complete.