Regular Expression Matching

Regular Expression Matching is a classic "looks scary, is actually a grid" problem. It supports two wildcards: . matches any single character, and * matches zero or more of the character before it. The trick is to stop thinking recursively and fill a 2-D table instead.

The slow way first

The natural first attempt is recursion: compare the front of s with the front of p, and whenever you hit an x*, branch into "use zero copies" and "use one more copy." That is correct, but the same subproblems — does the rest of s match the rest of p? — get solved over and over, giving exponential time in the worst case.

The question to ask: how many genuinely different subproblems are there? Only one per (i, j) pair, where i is how much of s we have consumed and j is how much of p. That is O(m·n) states — small enough to fill a table directly.

The idea: a True/False grid

Define dp[i][j] = does the first i characters of s match the first j characters of p. We fill the grid top-left to bottom-right, and the bottom-right cell is the answer.

Three cases per cell. If p[j-1] is a normal char or . that matches s[i-1], the cell inherits the diagonal dp[i-1][j-1]. If p[j-1] is *, we either drop the x* entirely (dp[i][j-2], the cell two columns left) or, if the starred char matches the current s char, consume that char and look up (dp[i-1][j]).

Walk through it

Step through the animation with s = "aab", p = "c*a*b". The top-left seed dp[0][0] is True (empty matches empty). The top row handles "empty string vs a pattern of stars." Then we fill inward: a* eats both a's, b matches b, and the bottom-right cell lights up True.

Pseudocode

dp[0][0] = True                          # empty s matches empty p
for j in 1..n:                           # empty s vs longer pattern
    if p[j-1] == '*':
        dp[0][j] = dp[0][j-2]            # the star takes zero chars
for i in 1..m:
    for j in 1..n:
        if p[j-1] matches s[i-1] or '.':
            dp[i][j] = dp[i-1][j-1]      # consume one matching char
        else if p[j-1] == '*':
            dp[i][j] = dp[i][j-2]        # zero copies of the starred char
            if p[j-2] matches s[i-1]:
                dp[i][j] = dp[i][j] or dp[i-1][j]   # one more copy
return dp[m][n]

The Python solution

def is_match(s, p):
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    for j in range(1, n + 1):
        if p[j - 1] == '*':
            dp[0][j] = dp[0][j - 2]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] in (s[i - 1], '.'):
                dp[i][j] = dp[i - 1][j - 1]
            elif p[j - 1] == '*':
                dp[i][j] = dp[i][j - 2]
                if p[j - 2] in (s[i - 1], '.'):
                    dp[i][j] = dp[i][j] or dp[i - 1][j]
    return dp[m][n]

• dp is sized (m+1) x (n+1) so row/column 0 can mean "the empty prefix."
• dp[0][0] = True is the seed: empty string matches empty pattern.
• The first loop fills the top row — only an x* can let a non-empty pattern still match the empty string, by taking zero characters (dp[0][j-2]).
• p[j - 1] in (s[i - 1], '.') is the plain-match case: a literal char that equals s[i-1], or a .. The cell copies the diagonal dp[i-1][j-1].
• For *, line 13 is the zero-use branch (skip the x*, look two columns left). Lines 14-15 add the one-more branch: if the starred char matches the current s char, OR in dp[i-1][j].
• The answer is dp[m][n] — the whole string against the whole pattern.

Complexity

Each of the (m+1)·(n+1) cells does O(1) work by reading at most three already-computed neighbors, so the whole table fills in O(m·n). Space can be reduced to O(n) by keeping only the previous row, but the full grid is clearer to reason about.

When this pattern shows up

Practice