A small but genuinely useful subset of regular expressions: . matches any single
character, and * matches zero or more of whatever came immediately
before it — a literal character or a .. The whole pattern must match the whole
string, start to end, the way ^pattern$ anchors it in a real regex engine. Every
other Backtracking entry on this site chooses a candidate from a small menu — a row for a queen, a
digit for a Sudoku cell, a direction out of a grid cell — and rejects it outright if it conflicts
with something already placed. This page's search never has more than two
candidates at any decision point, and neither one is ever illegal on its own: at a *,
the search can either treat it as matching zero repetitions (skip the pair
entirely and move on in the pattern) or as matching one more repetition (consume
one character of the string and stay on the same * to decide again). Both are always
worth trying — which is exactly why undoing a wrong guess and trying the other one is still
backtracking, just over a binary choice instead of a list of options.
A fixed string, aab, and a fixed pattern, c*a*b, not user-editable,
same convention as this site's other fixed-content interactive demos. The pattern opens with
c* — and c never appears in the string at all, so the very first decision
must be the zero-occurrence one. Step through and watch the string pointer and pattern pointer
move independently: the string pointer only ever advances (a character, once consumed along a
branch, stays consumed for the rest of that branch), while the pattern pointer can jump
backward when a deeper attempt fails and the search returns to try the other candidate at
a shallower *.
At every position, matchHere(si, pi) asks one question: can the rest of the
pattern, from pi onward, match the rest of the string, from si onward?
If the pattern is exhausted, the answer is whatever si being exhausted too says. If
the next pattern token is followed by *, the answer is "yes if skipping it works, or
if the current characters match and consuming one and re-asking the same question works" — an
OR across exactly those two recursive calls, never more. Otherwise it's a single
character check followed by advancing both pointers by one. On this page's own aab
vs. c*a*b, that reaches MATCH after 8 recursive
calls — computed directly from the demo's own reference implementation below, not estimated: the
leading c* is skipped immediately (1 call), then a* tries to consume
zero a's first (fails — a lone b can't match two leftover string characters), backs
up and consumes one a at a time until exactly two are eaten, at which point the
trailing literal b lines up with the string's own final character. That's
2 rejected literal comparisons and 2 backtracks (each one a
failed zero-occurrence attempt falling back to "consume one more") before the third accepted path
reaches the end of both sequences at once.
function isMatch(s, p) {
const n = s.length, m = p.length;
function matchHere(si, pi) {
if (pi === m) return si === n; // pattern exhausted: only ok if string is too
const firstMatch = si < n && (p[pi] === s[si] || p[pi] === '.');
if (pi + 1 < m && p[pi + 1] === '*') {
// try zero occurrences of p[pi], or (if it matches here) one more and re-ask the same *
return matchHere(si, pi + 2) ||
(firstMatch && matchHere(si + 1, pi));
}
return firstMatch && matchHere(si + 1, pi + 1);
}
return matchHere(0, 0);
}Verified against JavaScript's own RegExp as an oracle — every pattern built from
this exact subset (literals, ., and * on the preceding token) is already
valid native regex syntax, so new RegExp('^' + p + '$').test(s) is a trustworthy
independent check, not a second copy of the same logic. Across 30,000 randomly
generated string/pattern pairs (2-letter alphabet, 0-6 characters each, patterns built from
literals, ., and randomly-attached *), 0 mismatches.
Treating * as "one or more," the way + actually works, instead
of "zero or more," is a one-line-shaped bug with a large blast radius. Drop the
matchHere(si, pi + 2) branch and only ever try consuming a repetition
(firstMatch && matchHere(si + 1, pi)), and the function still runs, still terminates,
and still gets plenty of cases right — it's wrong precisely whenever a real solution needs a
* to vanish entirely. Minimal counterexample: s = "b",
p = "a*b". The true answer is true (zero as, then
b) — the buggy version reports false, because it never considers
skipping a* and immediately fails the literal check against a. Checked
against the same oracle across 30,000 fresh random pairs: wrong on 18.3% of them —
not a rare edge case, since a pattern's * group matching nothing at all is one of the
two outcomes it's specifically supposed to support, not a boundary condition bolted on
afterward.
Without memoization, overlapping * groups make the search
genuinely exponential, not just "slow on pathological input" in the abstract. Chain
several x* groups in front of a literal the string never ends in, and every way of
splitting the string's characters across those groups has to be tried and rejected before the
search can conclude no match exists — this is the same failure mode behind real-world
"catastrophic backtracking" / ReDoS reports against production regex engines, measured here
directly rather than just named. Instrumented with a call counter (not reproducible in this page's
own 8-call demo, which was picked to be small enough to step through by hand): the pattern
a*a*a*a*b (4 chained groups) against aaaa (4 a's, no trailing
b, so it must fail) costs 195 calls; against aaaaaaaa (8
a's) it costs 1,209. Scale both the chain length and the string together and it
gets much worse fast: a*a*a*a*a*a*a*a*a*a*a*a*b (12 groups) against 12 a's costs
7,904,455 calls; against 16 a's it costs 82,317,689 — a
10.4× jump from adding just 4 more characters, not a fixed additive cost. Nothing about the
answer changes (every one of these correctly reports no match); what changes is how long
the naive search takes to become sure of that negative.
Time: exponential in the worst case. Each * decision branches
into two recursive calls, and unlike every other Backtracking entry on this site, neither branch
is illegal on its own — both can be, and on adversarial input like the chained-star pattern above,
both regularly are, worth exploring fully. There is no known way to bound this naive recursion
below exponential in general. A well-known fix does exist and isn't built here: since every call is
fully determined by the pair (si, pi), and there are only (n+1)·(m+1)
such pairs, memoizing on that pair turns the same recursion into an O(n·m)
dynamic-programming table — the identical relationship
0/1 Knapsack has to
Subset Sum: a polynomial table exists for this exact
question, this page's own search just doesn't build it, to keep the demo focused on the
backtracking mechanism the Pitfalls section above measures the cost of. Space:
O(n+m) for the recursion stack in the naive version — no table, no memo, only the
current call chain is ever held at once.
See Choosing a Backtracking Strategy for how this page's two-candidates-and-neither-illegal shape compares to the other eleven entries' own rejection rules.