0

Regex matcher with starred groups

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Regex matcher with starred groups

Companies: Amazon

Difficulty: Hard

Problem statement

Implement a small regex engine for a text-processing pipeline. Write is_match(s: str, pattern: str) -> bool. It returns True only when the whole string s matches pattern.

The pattern uses these rules:

  • It contains only lowercase English letters, ., *, (, and ).
  • A letter matches itself. . matches exactly one lowercase letter.
  • x* matches zero or more copies of the single unit x just before the star.
  • ( ... ) groups its contents into one unit. A * after ) repeats the whole group, so (ab)* matches "", "ab", "abab", and so on. A group without a star matches its contents once.
  • Groups are never nested, and a * never appears inside a group. Every * follows a letter, a ., or a ).

Constraints: 0 <= len(s) <= 1000, 0 <= len(pattern) <= 1000, and s contains only lowercase letters.

Example 1

s = "zebeb", pattern = "(ze)*(be)*"
Output: False

(ze)* can take "ze" and (be)* can take "be", but the final "b" is only part of a group, and a starred group repeats only whole copies. No split works.

Example 2

s = "rrtuvtuvw", pattern = "r*(tuv)*w"
Output: True

r* matches "rr", (tuv)* matches "tuvtuv", and w matches "w".

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

This is the classic ./* regex match with one twist: a * can follow a parenthesized group, so a starred unit can be several characters long. The trick is to see that groups add very little once the pattern is tokenized well.

Tokenize first. Walk the pattern once and produce a list of tokens (unit, star):

  • A letter or . is a unit of length 1.
  • ( ... ) is a unit whose body is the text between the parentheses. There is no nesting, so the next ) closes it.
  • A * right after a unit sets star = True on that unit.
  • A group without a star is just a run of plain characters, so expand it into one token per character. After this step only starred tokens can be longer than one character.
  • An empty group () or ()* matches only the empty string, so drop it. Keeping a starred empty unit would let the recursion loop forever without consuming input.

Brute force. Recurse on (token index i, string index j). A plain token must match s[j] and move to (i+1, j+1). A starred token either matches zero times, going to (i+1, j), or matches its whole body once at j and stays on the same token at (i, j+len(body)). Without memoization this branches exponentially on inputs like a*a*a*...b.

Dynamic programming. There are only T * (n+1) states, so memoize them, or fill a table. Let dp[i][j] be true when tokens[i:] matches s[j:] exactly.

  • Base case: dp[T][j] is true only for j = n.
  • Plain token: dp[i][j] = matches(unit, s, j) and dp[i+1][j+1].
  • Starred token of length L: dp[i][j] = dp[i+1][j] or (matches(unit, s, j) and dp[i][j+L]).

Why it is correct. A starred unit used k times is the same as "use it once, then the rest is still a starred unit used k-1 times". So the self-reference to dp[i][j+L] covers every repeat count. That reference always points to a larger j, because L >= 1 after empty groups are dropped. So filling j from right to left inside each row never reads a value that is not ready yet. Each row needs only the row after it, so two arrays of length n+1 are enough.

Invariant. After row i is filled, cur[j] answers whether the pattern suffix that starts at token i matches the string suffix that starts at j, for every j.

Code

from dataclasses import dataclass


@dataclass(frozen=True)
class Token:
    unit: str       # one char, or the body of a group, e.g. "ab." for "(ab.)"
    star: bool      # True if the unit repeats zero or more times


def tokenize(pattern: str) -> list[Token]:
    """Split the pattern into units; a '*' attaches to the unit before it."""
    tokens: list[Token] = []
    i, n = 0, len(pattern)
    while i < n:
        if pattern[i] == "(":
            close = pattern.index(")", i)        # no nesting, so the next ')' closes
            unit, i = pattern[i + 1:close], close + 1
        elif pattern[i] in ")*":
            raise ValueError(f"unexpected {pattern[i]!r} at {i}")
        else:
            unit, i = pattern[i], i + 1
        star = i < n and pattern[i] == "*"
        if star:
            i += 1
        if not unit:
            continue                              # "()" or "()*" matches only ""
        if star or len(unit) == 1:
            tokens.append(Token(unit, star))
        else:                                     # an unstarred group is just its letters
            tokens.extend(Token(c, False) for c in unit)
    return tokens


def unit_matches(unit: str, s: str, j: int) -> bool:
    """Does `unit` match s[j : j + len(unit)] exactly?"""
    if j + len(unit) > len(s):
        return False
    return all(p == "." or p == s[j + k] for k, p in enumerate(unit))


def is_match(s: str, pattern: str) -> bool:
    tokens = tokenize(pattern)
    n, t = len(s), len(tokens)
    # dp[i][j]: tokens[i:] match s[j:] exactly.
    nxt = [False] * (n + 1)
    nxt[n] = True                                 # no tokens left matches only ""
    for i in range(t - 1, -1, -1):
        unit, star = tokens[i].unit, tokens[i].star
        size = len(unit)
        cur = [False] * (n + 1)
        for j in range(n, -1, -1):                # right to left: cur[j + size] is ready
            here = unit_matches(unit, s, j)
            if star:
                cur[j] = nxt[j] or (here and cur[j + size])
            else:
                cur[j] = here and nxt[j + size]
        nxt = cur
    return nxt[0]

Complexity

Let n = len(s), m = len(pattern), and T be the token count (T <= m).

  • Tokenizing: O(m) time, O(m) space.
  • Matching: each state (i, j) compares at most len(unit_i) characters. Summed over the tokens, that is O(n * m) time in the worst case. When every unit has length 1 this is the classic O(n * T).
  • Space: O(n) for the two DP rows plus O(m) for the tokens. If the interviewer wants a reconstructed match path, keep the full O(n * T) table.

Test cases

  • is_match("", "") returns True.
  • is_match("a", "") returns False.
  • is_match("", "a*(bc)*") returns True (every unit repeats zero times).
  • is_match("abcabc", "(abc)*") returns True.
  • is_match("abcab", "(abc)*") returns False (a partial group does not count).
  • is_match("xyxyz", "(xy)*z") returns True, and is_match("z", "(xy)*z") returns True.
  • is_match("abab", "(a.)*") returns True, and is_match("aba", "(a.)*") returns False.
  • is_match("aaab", "a*(ab)*") returns True (a* takes only two as, so a greedy match would fail).
  • is_match("cat", "(ca)t") returns True (an unstarred group is a plain literal).
  • is_match("mississippi", "mis*(is)*s*ip*.") returns True.
  • is_match("ab", ".") returns False (. matches exactly one letter).
  • is_match("qq", ".*") returns True.
  • is_match("hello", "()*hello()") returns True (empty groups are ignored).
  • is_match("aab", "(ab)*") returns False.

Follow-ups

  1. Find, not full match. Return whether the pattern matches some substring of s, or the first such span. Make the base case dp[T][j] = True for every j, and try every start index. You can also add an implicit .* before the pattern. To get the span, store the end index instead of a boolean.
  2. More quantifiers (+, ?). x+ is x x*, which the tokenizer can rewrite. x? is a token with the transition dp[i+1][j] or (match and dp[i+1][j+L]). Bounded repeats {a,b} add a repeat counter to the state, or expand into copies.
  3. Alternation and nested groups ((ab|c)*, ((ab)*c)*). Fixed-length units no longer work. Compile the pattern to a Thompson NFA, with epsilon edges for * and |. Then simulate the set of active states over the string, in O(n * m) time with no backtracking. This is also the answer to "why not backtracking?": it avoids catastrophic backtracking (ReDoS).
  4. Many strings, one pattern. Tokenize or compile once and reuse the result for every string. For heavy reuse, turn the NFA into a DFA with subset construction, built lazily and cached, so each string runs in O(n).
  5. Streaming input. The string arrives one character at a time. Run the DP forward instead: keep the set of token positions reachable after each prefix (an NFA frontier) and report a match whenever the end position is in the set. The memory stays O(T), whatever the stream length.

Interviewer expectations

Mid-level (L4)

  • Clarifies the rules: full match or substring, empty group, a * with nothing before it, and empty inputs.
  • Gets the recursive "zero or one more" idea for *, then adds memoization.
  • Handles starred groups correctly, including a partial final repeat that must fail.

Senior (L5)

  • Separates parsing from matching, and treats unstarred groups as literals.
  • Writes the bottom-up DP with the right fill order and explains why L >= 1 keeps it well founded.
  • States the time and space complexity precisely and reduces space to two rows.
  • Tests greedy traps like a*(ab)* without being prompted.

Staff (L6+)

  • Explains why the restrictions (no nesting, no * inside groups) make fixed-length units possible, and what changes without them.
  • Moves to an NFA (Thompson construction) for alternation and nesting, and discusses ReDoS and the trade-offs of a lazy DFA.
  • Talks about production concerns: compiling and caching patterns, input limits, streaming, and returning match spans for the NLP use case.

Sign in to comment, vote or remix.