Regular Expression Matching

1. Problem & Core Objective

Implement regular expression matching supporting . and *:

• . matches any single character
• * matches zero or more of the preceding element

The match must cover the entire input string.

s = "aa",    p = "a"      →  false
s = "aa",    p = "a*"     →  true
s = "ab",    p = ".*"     →  true      ".*" = any sequence
s = "mississippi", p = "mis*is*p*."  →  false

Constraints: 1 <= s.length <= 20 · 1 <= p.length <= 20 · s is lowercase; p is lowercase plus . and * · every * has a valid preceding element

What's actually being tested: that * binds to the preceding character and is therefore processed as a two-character unit, and that its "zero or more" nature forces two branches — take zero, or consume one and stay. It's the hardest recurrence in the section because the pattern index doesn't advance uniformly.

2. First-Principles Thought Process

* is not a standalone token

a* is one unit meaning "zero or more a". So when scanning the pattern, seeing p[j] you must look ahead at p[j+1] to know whether p[j] is a plain character or the base of a star.

Equivalently, working backwards from dp[i][j], the relevant question is whether p[j-1] is a *, in which case p[j-2] is its base.

Processing * as a separate token is the first wrong turn — it has no meaning without what precedes it.

The two branches of *

When p[j-1] is * with base p[j-2]:

Use it zero times. Discard the whole two-character unit and match the rest:

dp[i][j] = dp[i][j-2]

Use it one more time. Only if the base matches s[i-1]. Consume that character of s but keep the pattern unit, since * can match again:

dp[i][j] |= dp[i-1][j]        note: j, not j-2

The dp[i-1][j] is the line people get wrong. The pattern index does not advance — that's what "zero or more" means. Advancing it would make * mean "exactly one".

The non-star case

If p[j-1] isn't a *, it must match s[i-1] — either exactly or via .:

dp[i][j] = dp[i-1][j-1] && (p[j-1] == s[i-1] || p[j-1] == '.')

The base case that's easy to miss

dp[0][0] = true — empty matches empty.

But row 0 is not all false. A pattern like a*b*c* matches the empty string, so:

for (int j = 2; j <= n; j++)
    if (p.charAt(j - 1) == '*') dp[0][j] = dp[0][j - 2];

Forgetting this makes s = "", p = "a*" return false. It's the single most common error in this problem.

Column 0 is all false for i > 0 — a non-empty string can't match an empty pattern.

3. Solution Paths

Approach 1 — Recursion

public boolean isMatch(String s, String p) {
    return match(s, p, 0, 0);
}

private boolean match(String s, String p, int i, int j) {
    if (j == p.length()) return i == s.length();            // pattern exhausted

    boolean first = i < s.length() &&
                    (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.');

    if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
        return match(s, p, i, j + 2)                         // use the star zero times
            || (first && match(s, p, i + 1, j));             // use it once more, keep pattern
    }
    return first && match(s, p, i + 1, j + 1);               // ordinary character
}

• Time exponential · Space O(i + j) stack

Counter-questions on this approach

⭐ "Why does the 'use it once more' branch pass j rather than j + 2?"

Because * means zero or more — after consuming one character of s, the same a* unit may match again.

Passing j + 2 would make it "exactly one", so "aaa" against "a*" would fail. Passing j keeps the star available, and the "zero times" branch is what eventually terminates it.

That pair — (i, j+2) for zero, (i+1, j) for one-more — is the entire semantics of *.

⭐ "Why look ahead at p[j+1] rather than treating * as its own token?"

Because * is meaningless alone — it modifies the preceding element. a* is a single unit.

Scanning forward, you must know whether the current character is plain or starred before deciding how to consume it, and that requires the lookahead. Treating * as a standalone token is the first wrong turn.

"Why first && before recursing?"

Short-circuiting: if the current characters don't match, consuming one from s is pointless. And it guards s.charAt(i) against i == s.length().

"How slow is it?"

Exponential on patterns with many stars — "aaaaaaaaaaaaaaaaaaaa" against "a*a*a*a*a*a*a*a*a*a*" explores an enormous number of splits. At the stated limits of 20 it survives, but it's the classic catastrophic-backtracking shape that affects real regex engines.

Approach 2 — Memoised recursion

public boolean isMatch(String s, String p) {
    return match(s, p, 0, 0, new Boolean[s.length() + 1][p.length() + 1]);
}

private boolean match(String s, String p, int i, int j, Boolean[][] memo) {
    if (memo[i][j] != null) return memo[i][j];
    if (j == p.length()) return memo[i][j] = (i == s.length());

    boolean first = i < s.length() &&
                    (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.');

    boolean result;
    if (j + 1 < p.length() && p.charAt(j + 1) == '*')
        result = match(s, p, i, j + 2, memo) || (first && match(s, p, i + 1, j, memo));
    else
        result = first && match(s, p, i + 1, j + 1, memo);

    return memo[i][j] = result;
}

• Time O(m · n) · Space O(m · n)

Counter-questions on this approach

⭐ "Why Boolean[][] rather than boolean[][]?"

Because false is a legitimate answer — most (i, j) pairs genuinely don't match. With boolean[][] defaulting to false, those would be recomputed forever.

null is outside the answer domain. Same discipline as Word Break.

"Why is the top-down version often preferred here?"

The lookahead at p[j+1] reads naturally forwards, and the base case j == p.length() is a clean stopping condition.

The bottom-up version has to look backwards at p[j-1] and p[j-2], plus seed row 0 explicitly — noticeably fiddlier for the same complexity. I'd write the memoised version by preference.

Approach 3 — Bottom-up tabulation

public boolean isMatch(String s, String p) {
    int m = s.length(), n = p.length();
    boolean[][] dp = new boolean[m + 1][n + 1];
    dp[0][0] = true;                                         // empty matches empty

    for (int j = 2; j <= n; j++)                             // patterns like a*b*c* match ""
        if (p.charAt(j - 1) == '*') dp[0][j] = dp[0][j - 2];

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) {
            char pc = p.charAt(j - 1);

            if (pc == '*') {
                char base = p.charAt(j - 2);
                dp[i][j] = dp[i][j - 2];                     // star used zero times
                if (base == '.' || base == s.charAt(i - 1))
                    dp[i][j] |= dp[i - 1][j];                // one more; pattern index STAYS
            } else {
                dp[i][j] = dp[i - 1][j - 1] &&
                           (pc == '.' || pc == s.charAt(i - 1));
            }
        }

    return dp[m][n];
}

Trace — s = "aa", p = "a*":

At dp[1][2]: star used zero times gives dp[1][0] = F; base a matches s[0], so |= dp[0][2] = T → T. At dp[2][2]: zero times gives dp[2][0] = F; base matches s[1], so |= dp[1][2] = T → T ✓

• Time O(m · n) · Space O(m · n)

Counter-questions on this approach

⭐ "Why must row 0 be seeded, and what breaks without it?"

Because a pattern of star-units matches the empty string. a*, a*b*, .* all match "".

Without the seeding loop, dp[0][2] would be false, and s = "" with p = "a*" returns false instead of true. Worse, it propagates: dp[i][j] for starred patterns reads dp[0][j-2], so the whole table is affected.

This is the single most common error in the problem, and Java's zero-initialisation makes it silent.

⭐ "Why does the loop start at j = 2?"

Because a * at j = 1 would have no preceding element, and p.charAt(j-2) would index -1.

The constraints guarantee every * has a valid predecessor, so a pattern never starts with *. Starting at 2 respects that without needing a check.

⭐ "In the star case, why dp[i-1][j] and not dp[i-1][j-2]?"

Because the star unit stays available. Consuming one character of s doesn't consume the pattern — a* can match another a immediately after.

dp[i-1][j-2] would mean "used exactly once and now done", making * behave like ?. On "aaa" against "a*" that returns false.

The j - 2 appears only in the zero-times branch, where the whole unit is discarded.

"Why |= rather than = in the second star branch?"

Because either branch suffices — it's an existence question. The zero-times result is computed first, and the one-more result can only add to it.

"Does .* correctly match anything?"

Yes. Base . matches any character, so the one-more branch always applies, letting it consume the whole string. And the zero-times branch lets it match empty. Together that's "any sequence including none".

"Can this be rolled to one row?"

Partially — dp[i][j] reads dp[i-1][j], dp[i-1][j-1] and dp[i][j-2]. The last is the current row, two columns back, so a single ascending row works if you also save the diagonal. Fiddly, and at 20 × 20 entirely unnecessary.

Comparison

4. Why the Optimal Wins

The recursion re-explores (i, j) pairs exponentially on star-heavy patterns — the same catastrophic backtracking that affects production regex engines.

Memoising collapses it to the m × n distinct states. This is one of the few problems in the section where top-down is the better end state: the lookahead at p[j+1] reads forwards naturally, whereas the bottom-up version must look backwards and seed row 0 by hand.

The framing worth keeping:

* binds to the preceding character, so a* is one two-character unit. It branches two ways: use it zero times (j + 2, pattern advances) or one more time (i + 1, pattern stays). And row 0 must be seeded, because a*b* matches the empty string.

5. Java Prerequisites

Lookahead for the star

if (j + 1 < p.length() && p.charAt(j + 1) == '*') { ... }    // top-down
if (p.charAt(j - 1) == '*') { char base = p.charAt(j - 2); }  // bottom-up

The two star branches

match(i, j + 2)                      // zero times: discard the unit
|| (first && match(i + 1, j))        // one more: consume s, KEEP the pattern

Row-0 seeding — the line most often missed:

for (int j = 2; j <= n; j++)
    if (p.charAt(j - 1) == '*') dp[0][j] = dp[0][j - 2];

Boolean[][] for memoisation — false is a real answer.

6. Interview Communication Guide

Clarifying questions: Must the match cover the entire string (yes — not a substring search)? Does * apply to the preceding character or the whole pattern (the preceding element)? Can the pattern start with * (no — guaranteed valid)? Is .* valid (yes — matches anything)?

The pitch

"The key structural point is that * binds to the preceding character, so a* is a single two-character unit meaning 'zero or more a'. Treating * as its own token is the first wrong turn — it's meaningless alone.

So when scanning the pattern I look ahead one character to decide whether the current one is plain or starred.

A star branches two ways. Zero times: discard the whole unit and advance the pattern by 2, leaving s untouched. One more time: only if the base matches the current character of s — consume that character, but keep the pattern index, because * can match again.

That second branch is the line people get wrong. Advancing the pattern there would make * mean 'exactly one', and 'aaa' against 'a*' would fail.

If the current pattern character isn't starred, it must match — exactly or via . — and both indices advance.

O(m · n) states, so memoising the recursion gives O(m·n) time and space. I'd use Boolean[][] rather than boolean[][], since false is a legitimate answer and a primitive array couldn't distinguish it from 'not computed'.

Bottom-up works too, but it needs one thing that's easy to miss: row 0 must be seeded. A pattern like a*b*c* matches the empty string, so dp[0][j] = dp[0][j-2] for each star. Without it, s = '' with p = 'a*' returns false — and it propagates, because starred patterns read dp[0][j-2].

I'd actually prefer the top-down version here, which is unusual for DP. The lookahead reads naturally forwards, and the base case is a clean j == p.length(). Bottom-up has to look backwards at p[j-1] and p[j-2] and seed row 0 by hand."

Edge cases to volunteer:

Name "" with "a*" and "aab" with "c*a*b". The first is the row-0 seeding; the second needs c* matched zero times, which fails if the zero-branch is missing.

7. Follow-Up Questions — Modified Constraints

⭐ "Add + meaning one or more."

a+ is a followed by a*. Either rewrite the pattern before matching, or add a branch requiring at least one match before allowing the star behaviour. The rewrite is cleaner and needs no new recurrence.

⭐ "Add ? meaning zero or one."

Two branches like *, but the "one" branch advances the pattern by 2 rather than keeping it — so it can't repeat. That contrast makes the j versus j+2 distinction concrete.

"Implement wildcard matching where * matches any sequence."

LeetCode 44, and simpler: * there is standalone, not bound to a preceding character. dp[i][j] = dp[i-1][j] || dp[i][j-1] — use it or don't. No lookahead needed, which shows how much of this problem's difficulty comes from the binding.

"What if the pattern had 10^4 characters?"

O(m·n) = 10^8 — borderline. Real engines compile the pattern to an NFA and simulate it, which is O(m·n) worst case but far better typically, and avoids the catastrophic backtracking that a naive recursive matcher exhibits.

"Return the matched groups."

That requires tracking positions through the DP, and with * a group's extent is ambiguous — you'd need a convention (leftmost-longest, typically). Genuinely more involved than the boolean.

"Why do real regex engines suffer catastrophic backtracking if this is O(m·n)?"

Because backreferences and lookarounds make the language non-regular, so the DP formulation no longer applies and they fall back to backtracking. Pure regular expressions — which this problem is — always admit the polynomial solution.