Blind Plus 100 Visualized

#95 · 2D DP

Regular Expression Matching

Implement regular expression matching with support for "." (any single character) and "*" (zero or more of the preceding element). The match must cover the entire input string.

HardLeetCode
  • Computing
  • Depends on
  • Answer
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

2D boolean DP table

dp[i][j] says whether the suffix s[i…] matches the suffix p[j…]. A starred element x* has two options: use it zero times (jump to j + 2) or, if the current character matches x, consume it and stay on the same element (i + 1, j). A plain element must match and advances both.

Memory layout

A (m + 1) × (n + 1) array of booleans, filled from the bottom-right.

OperationCost
timeO(m · n)
spaceO(m · n)

Set of automaton states

Compile the pattern into a tiny NFA (a position in the pattern is a state, x* adds a free skip). Reading a character moves every active state; the answer is whether the final state is active at the end. This is the idea inside real regex engines.

Memory layout

Two boolean arrays of length n + 1 (current and next).

OperationCost
timeO(m · n)
spaceO(n)

Why it fits

  • Only the position in the string and the position in the pattern matter, so the number of distinct subproblems is (m + 1)(n + 1) even though the number of ways to expand stars is exponential.
  • Star is the only source of branching: zero copies or one more. Both options point to smaller subproblems, which is precisely a DP recurrence.
  • The NFA view shows the same table can be generated row by row, which lets you drop everything but one row of memory.

Why alternatives degrade

Greedy matching (consume as many as possible):
a*a against "aa" fails if the star takes both a's; the star must be able to give characters back.
Backtracking without a cache:
Patterns such as a*a*a*a*b on "aaaa…" take exponential time.
Translating to a library regex:
Not allowed here, and library engines can themselves backtrack exponentially.

Four approaches, from naive to production

1 · beginner

Plain recursion

time O(2^(m+n)) worst casespace O(m + n)

match(i, j) compares the next characters. For x* try zero uses first, then (if x matches) consume one character and stay on x*. Plain elements must match and advance both pointers.

bool isMatch(string s, string p) {
    function<bool(int, int)> match = [&](int i, int j) -> bool {
        if (j == (int)p.size()) return i == (int)s.size();
        bool first = i < (int)s.size() && (p[j] == '.' || p[j] == s[i]);
        if (j + 1 < (int)p.size() && p[j + 1] == '*') {
            return match(i, j + 2) || (first && match(i + 1, j));
        }
        return first && match(i + 1, j + 1);
    };
    return match(0, 0);
}

Flaws & bottlenecks

  • The same (i, j) state is reached through many different star expansions.
  • Patterns like a*a*a*b against "aaaa…" blow up exponentially.
  • Deep recursion on long strings.

Interviewer cross-questions

Why try zero occurrences first?

Say: Either order works; trying zero first avoids consuming characters unnecessarily, and the || short-circuits as soon as one branch succeeds.

What does "first" mean?

Say: Whether the current pattern character can match the current string character: the string is not used up and the pattern char is "." or equal.

Why is greedy matching wrong?

Say: A star that eats too much cannot give characters back, so a*a would reject "aa". Recursion tries every split.

2 · intermediate

Memoised recursion

time O(m · n)space O(m · n)

Cache match(i, j) in a map keyed by i · (n + 1) + j, so each state is evaluated at most once.

bool isMatch(string s, string p) {
    unordered_map<int, bool> memo;
    function<bool(int, int)> match = [&](int i, int j) -> bool {
        if (j == (int)p.size()) return i == (int)s.size();
        int key = i * ((int)p.size() + 1) + j;
        auto it = memo.find(key);
        if (it != memo.end()) return it->second;
        bool first = i < (int)s.size() && (p[j] == '.' || p[j] == s[i]);
        bool result;
        if (j + 1 < (int)p.size() && p[j + 1] == '*') result = match(i, j + 2) || (first && match(i + 1, j));
        else result = first && match(i + 1, j + 1);
        memo[key] = result;
        return result;
    };
    return match(0, 0);
}

Flaws & bottlenecks

  • Recursion depth up to m + n.
  • Hash map overhead; a 2D array is faster.
  • Allocates for every visited state.

Interviewer cross-questions

Why is the number of states only (m + 1)(n + 1)?

Say: The future depends only on the two positions, not on how we got there.

Why does the base case ignore the cache?

Say: It is O(1) anyway.

How do you avoid recursion?

Say: Fill the table bottom-up from the end of both strings.

3 · advanced

Bottom-up table

time O(m · n)space O(m · n)

Fill dp from the end of both strings. dp[m][n] = true; for each cell, a starred element is dp[i][j+2] || (first && dp[i+1][j]); a plain element is first && dp[i+1][j+1].

bool isMatch(string s, string p) {
    int m = s.size(), n = p.size();
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
    dp[m][n] = true;
    for (int i = m; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            bool first = i < m && (p[j] == '.' || p[j] == s[i]);
            if (j + 1 < n && p[j + 1] == '*') dp[i][j] = dp[i][j + 2] || (first && dp[i + 1][j]);
            else dp[i][j] = first && dp[i + 1][j + 1];
        }
    }
    return dp[0][0];
}

Flaws & bottlenecks

  • O(m · n) memory.
  • Evaluates cells that cannot affect dp[0][0].
  • The star recurrence is easy to get backwards (zero uses vs one more).

Interviewer cross-questions

Why start at dp[m][n]?

Say: The empty string matches the empty pattern; all other base cases follow from the recurrence (row m only matches patterns made of starred pieces).

How is "a*" against "" handled?

Say: dp[m][0] = dp[m][2] because zero uses of a* is allowed, and dp[m][2] = true when the rest is empty.

Can the table shrink?

Say: Yes: each row needs only the row below, giving O(n) space.

4 · expert

NFA state-set simulation

time O(m · n)space O(n)

Treat each pattern position as an automaton state. Keep the set of reachable states; after each character move every active state that matches it (stay on x*, advance on a plain piece) and add the free skips of starred pieces.

bool isMatch(string s, string p) {
    int n = p.size();
    auto closure = [&](vector<bool>& set) {
        for (int j = 0; j + 1 < n; j++) {
            if (set[j] && p[j + 1] == '*') set[j + 2] = true;
        }
    };
    vector<bool> states(n + 1, false);
    states[0] = true;
    closure(states);
    for (char c : s) {
        vector<bool> next(n + 1, false);
        for (int j = 0; j < n; j++) {
            if (!states[j] || (p[j] != '.' && p[j] != c)) continue;
            if (j + 1 < n && p[j + 1] == '*') next[j] = true;
            else next[j + 1] = true;
        }
        closure(next);
        states = next;
    }
    return states[n];
}

Flaws & bottlenecks

  • Less obvious than the DP derivation.
  • Assumes a valid pattern (every * has a preceding element).
  • Gives only a yes / no answer, with no match positions.

Interviewer cross-questions

Why is this immune to exponential blow-up?

Say: It tracks the set of all possible positions at once instead of exploring them one by one, so there is no backtracking.

How is it related to the DP table?

Say: Row i of the forward table (is state j reachable after i characters?) is exactly the state set; the DP just stores all rows.

What are the edge cases?

Say: Empty string with a pattern of starred pieces (true), a pattern starting with ".*", stars chained like a*b*c*, and a pattern longer than the string.

Synchronized code walkthrough

Showing: Plain recursion — shares the player above; click any step to jump.

bool isMatch(string s, string p) {
    function<bool(int, int)> match = [&](int i, int j) -> bool {
        if (j == (int)p.size()) return i == (int)s.size();
        bool first = i < (int)s.size() && (p[j] == '.' || p[j] == s[i]);
        if (j + 1 < (int)p.size() && p[j + 1] == '*') {
            return match(i, j + 2) || (first && match(i + 1, j));
        }
        return first && match(i + 1, j + 1);
    };
    return match(0, 0);
}