Regular Expression Matching, in depth: the dot-star recurrence, a worked table, three verified implementations and the link to automata

The exact problem

Pin the semantics down before writing code, because most wrong answers come from a fuzzy specification. The match is anchored at both ends: a does not match ab. A . matches exactly one character. A * is not a token on its own; it modifies the element just before it, so a* is one unit meaning zero or more a, and .* means zero or more of any character. A pattern that starts with * or contains ** is malformed and should be rejected at the boundary, not silently treated as a literal.

These rules agree with Python re.fullmatch restricted to the same alphabet, which gives us a free oracle for testing later. There is no alternation, grouping, + or ?; the last two are added at the end.

Why plain recursion explodes

The direct approach reads the pattern left to right. Without a star, the first characters must match and we recurse on both tails. With a star, we either use the element zero times (drop it from the pattern) or once more (drop one character from the string and keep the pattern).

def naive(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 naive(s, p[2:]) or (first and naive(s[1:], p))
    return first and naive(s[1:], p[1:])

This is correct, and on friendly inputs it is fast. The trouble is that the two branches of a star overlap. With several stars in a row, many different splits of the string reach the same pair of remaining suffixes, and the recursion re-solves each pair from scratch. Matching fourteen a characters against a*a*...a*c (which can never match, because there is no c) produced these call counts when we ran the function above:

The right-hand column is the whole point. The function only ever asks about a suffix of s and a suffix of p, so there are at most (m+1)(n+1) different questions. Millions of calls are spent answering a few hundred questions over and over. That is the textbook signature of a problem that wants memoisation, the same signature you see in longest common subsequence.

Defining the state and the recurrence

Define dp[i][j] as: does the suffix s[i:] match the suffix p[j:]? The answer we want is dp[0][0]. Let first mean that i < len(s) and p[j] is either s[i] or a dot. Then there are exactly three cases.

1. Base case: dp[m][n] is true (empty matches empty). Any other dp[i][n] with i < m is false, because an empty pattern cannot consume characters.
2. If p[j+1] is a star: dp[i][j] = dp[i][j+2] or (first and dp[i+1][j]). The first term uses the starred element zero times; the second consumes one character and stays on the same pattern position, so the star can consume again.
3. Otherwise: dp[i][j] = first and dp[i+1][j+1].

Each cell depends only on cells with a larger i or a larger j, so filling rows from i = m down to 0, and within a row from j = n - 1 down to 0, always reads cells that are already final. Notice that row m (the empty string) is not all false: dp[m][j] is true when the rest of the pattern is entirely starred elements, such as a*b*. The recurrence handles this for free, because first is false there and only the skip branch can succeed.

Three implementations

Two listings follow, plus a third variant described here. All were checked against the edge cases in the testing section and against re.fullmatch on twenty thousand random strings and patterns over {a, b, .}. The top-down version is the naive function rewritten over indices (i, j) instead of string slices, with functools.lru_cache on it: a correct recursion plus a cache is the quickest way to a correct DP. The bottom-up version fills the table explicitly. It has no recursion depth limit, which matters in Python, where the default limit of about a thousand frames is reachable with long inputs:

def is_match(s: str, p: str) -> bool:
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[m][n] = True
    for i in range(m, -1, -1):
        for j in range(n - 1, -1, -1):
            first = i < m and p[j] in (s[i], ".")
            if j + 1 < n and p[j + 1] == "*":
                dp[i][j] = dp[i][j + 2] or (first and dp[i + 1][j])
            else:
                dp[i][j] = first and dp[i + 1][j + 1]
    return dp[0][0]

Row i reads only row i and row i+1, so two rows are enough. This cuts memory from O(mn) to O(n), which is the version to ship when the string is long and the pattern is short:

def is_match_rolling(s: str, p: str) -> bool:
    m, n = len(s), len(p)
    nxt = [False] * (n + 1)              # row i + 1
    for i in range(m, -1, -1):
        cur = [False] * (n + 1)          # row i
        cur[n] = (i == m)
        for j in range(n - 1, -1, -1):
            first = i < m and p[j] in (s[i], ".")
            if j + 1 < n and p[j + 1] == "*":
                cur[j] = cur[j + 2] or (first and nxt[j])
            else:
                cur[j] = first and nxt[j + 1]
        nxt = cur
    return nxt[0]

Time is O(mn) for all three: each cell does constant work. The memoised variant can be faster in practice, because it only visits reachable cells and stops as soon as an or short-circuits.

Worked example: aab against c*a*b

Take s = aab and p = c*a*b. The pattern positions are 0 c, 1 *, 2 a, 3 *, 4 b, plus the end at 5. The diagram shows the completed table.

Walk the important cells. Bottom row, i = 3 (empty string): only dp[3][5] is true, because the remaining b needs a character. Row 2 (b): dp[2][4] is true since b matches b and dp[3][5] is true. Then dp[2][2] sees a*; the skip branch reads dp[2][4], true. And dp[2][0] sees c*; skip reads dp[2][2], true.

Row 1 (ab): dp[1][2] can skip to dp[1][4], which is false because a is not b, but first is true and the consume branch reads dp[2][2], true. Row 0 repeats the pattern: dp[0][2] consumes into dp[1][2], and dp[0][0] skips c* into dp[0][2]. The answer is true: c* matched nothing, a* matched aa, and b matched b.

The table is an automaton

Read the table one row at a time and it is a nondeterministic automaton in disguise. Treat each pattern position j as a state. The set of j where row i is true is the set of states from which the rest of the string can be accepted. Moving from row i+1 to row i is one step of simulating all states in lockstep, and the skip branch is the epsilon move past a starred element. This is Thompson-style simulation run backwards, and it is why both approaches share the same O(mn) bound.

The practical lesson is about backtracking. Many regex libraries, including those in Python, Java, JavaScript and PCRE, use backtracking engines that behave like the naive function: fine on typical inputs, exponential on adversarial ones. The table, or an automaton engine such as RE2 or the Rust regex crate, guarantees linear time in the input for a fixed pattern. If a user can influence either the pattern or a long input, that guarantee is the difference between a slow request and a denial of service. See backtracking for the general technique.

Extending to plus, question mark and classes

Real matchers need more than . and *. The clean way to extend the recurrence is to tokenise the pattern first into elements, each with a predicate and a quantifier, so the DP never inspects raw characters:

def tokenize(p):
    toks, j = [], 0
    while j < len(p):
        if p[j] in "*+?":
            raise ValueError(f"quantifier with nothing to repeat at {j}")
        atom = p[j]; j += 1
        q = p[j] if j < len(p) and p[j] in "*+?" else ""
        j += len(q)
        toks.append((atom, q))
    return toks

def match_tokens(s, toks):
    m, n = len(s), len(toks)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[m][n] = True
    for i in range(m, -1, -1):
        for k in range(n - 1, -1, -1):
            atom, q = toks[k]
            first = i < m and atom in (s[i], ".")
            if q == "*":
                dp[i][k] = dp[i][k + 1] or (first and dp[i + 1][k])
            elif q == "+":
                dp[i][k] = first and (dp[i + 1][k] or dp[i + 1][k + 1])
            elif q == "?":
                dp[i][k] = dp[i][k + 1] or (first and dp[i + 1][k + 1])
            else:
                dp[i][k] = first and dp[i + 1][k + 1]
    return dp[0][0]

Plus means one match followed by zero or more, so it consumes a character and then either stays or moves on. Question mark either skips or consumes exactly one. Character classes only change first: replace the equality test with a set membership or range check. Groups and alternation break the flat structure, and at that point you should build an automaton instead of growing the table.

Failure modes and how to test for them

The bugs in this problem are predictable, so test for them by name.

• Reading past the pattern. Checking p[j+1] without j + 1 < n raises an index error on the last element, or in languages without bounds checks, reads garbage.
• Forgetting that the empty string can match. Initialising the whole bottom row to false breaks ('', 'a*'). Start the outer loop at i = m so the bottom row is computed, not assumed.
• Treating star as a token. Code that handles * when it sees it, rather than looking ahead from the element it modifies, gets ('aaa', 'a*a') wrong.
• Accepting malformed patterns. A leading star or a double star should be a validation error at the API boundary, as the tokeniser above does.
• Prefix matching by accident. Returning true when the pattern is exhausted, without checking that the string is also exhausted, turns a full match into a prefix match.

The cheapest strong test is differential: generate short random strings and patterns, compare against re.fullmatch, and keep the failing pair when they disagree. Pin the classic cases too: ('mississippi', 'mis*is*p*.') is false and ('', '.*.*') is true.

Operational guidance

This matcher suits simple wildcard rules that need a hard performance guarantee: routing rules, allowlists, feature flag targeting, log filters and permission scopes.

• Cap both lengths. A 10,000-character string against a 100-element pattern is a million cells, cheap; unbounded user input is not.
• Precompile once. Tokenise and validate each pattern when the rule is saved, not on every request, and reject bad patterns with a message that names the position.
• Prefer a linear-time engine for full regex. If users need groups or alternation, use RE2 or a similar automaton engine rather than extending this table or exposing a backtracking library to untrusted patterns.

Trade-offs

What to do next

• Write the recurrence from memory, then implement the bottom-up version and run it on the six edge cases above.
• Add a differential fuzz test against re.fullmatch and leave it in your test suite.
• Convert to rolling rows and confirm memory stays flat as the input string grows.
• Extend with + and ? through a tokeniser, and add a character-class predicate.
• Find every place your services run user-influenced regex on a backtracking engine and add length caps or move them to a linear-time engine.
• Solve the related wildcard problem, where * matches any sequence on its own, and compare the two recurrences.