CODING CHALLENGE · N°38

Mini Regex Matcher (. and *)

Hard Dynamic ProgrammingStringsRecursion

Implement regular-expression matching with "." (any single char) and "*" (zero-or-more of the preceding element) — the classic hard interview problem. The whole subtlety is that "*" can match nothing or many, so you must explore both. Solve it with DP in Python or TypeScript, with hidden tests.

The problem

Implement is_match(s, p): does the pattern p match the entire string s? Two special characters: . matches any single character, and * matches zero or more of the element immediately before it. The match must cover all of s, not just a prefix.

EXAMPLE 1

Input s = 'aa', p = 'a'

Output False

"a" does not cover both characters

EXAMPLE 2

Input s = 'aa', p = 'a*'

Output True

"a*" matches zero-or-more copies of a

EXAMPLE 3

Input s = 'ab', p = '.*'

Output True

".*" matches any sequence

EXAMPLE 4

Input s = 'aab', p = 'c*a*b'

Output True

"c*" matches zero c, "a*" matches two a

CONSTRAINTS

A * always follows a valid element (a letter or .) — it never appears first.
The match is full-string: the pattern must consume all of s.
Because * can match zero or many, you must try both branches — a recursion with memoization or a 2-D DP does it in O(m·n).

SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement is_match(s, p) with DP. Let dp[i][j] mean "does s[i:] match p[j:]?" Fill it from the end. Handle a * at p[j+1] by either skipping the pair (zero matches) or consuming one char of s (if it matches) and staying on the same pattern element.

HINTS — 4 IDEAS

Work backwards: dp[i][j] = does s[i:] match p[j:]? The base case dp[len(s)][len(p)] = True.
Let first = i < len(s) and (p[j] == s[i] or p[j] == ".") — does the current char match here?
If the next pattern char is *: dp[i][j] = dp[i][j+2] (use zero) or (first and dp[i+1][j]) (use one, stay).
Otherwise: dp[i][j] = first and dp[i+1][j+1]. The answer is dp[0][0].

CPython · WebAssembly

Approach, complexity & discussion — open after you solve

The approach

Match a pattern with . (any single character) and * (zero or more of the preceding element) against a string. The key case is *: try matching zero occurrences (skip the x* in the pattern) or, if the current character matches, consume one and stay on the same pattern position. Use DP or memoized recursion so the two branches do not blow up.

Complexity

Time O(n·m) with memoization or DP; naive recursion can be exponential on adversarial inputs.

Common mistakes

Handling * greedily without the zero-match branch — you miss valid matches.
Letting . match past the end of the string.
No memoization, so overlapping subproblems explode exponentially.

Where this shows up

This tiny matcher is the conceptual core of regular expressions. Real engines compile to an NFA/DFA for speed, but the “* means try both branches” recursion is the same idea — and it explains catastrophic backtracking, the pathological slowdown behind real-world ReDoS bugs.

Finished this one? 0 / 75 Challenges done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

Mini Regex Matcher (. and *)

The problem

Your turn — write it

The approach

Complexity

Common mistakes

Where this shows up

Explore the topic

More Challenges

Explore more from Vibe Engines