Vibe Engines Learn
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
  1. Work backwards: dp[i][j] = does s[i:] match p[j:]? The base case dp[len(s)][len(p)] = True.
  2. Let first = i < len(s) and (p[j] == s[i] or p[j] == ".") — does the current char match here?
  3. 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).
  4. Otherwise: dp[i][j] = first and dp[i+1][j+1]. The answer is dp[0][0].
CPython · WebAssembly

Explore the topic

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

Algorithms & DSA