Regular Expression Matching — The Hardest 2D DP String Problem in FAANG Interviews

Problem Statement#

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:

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

The matching must cover the entire input string (not partial).

Constraints:

• 1 <= s.length <= 20
• 1 <= p.length <= 30
• s contains only lowercase English letters
• p contains only lowercase English letters, '.', and '*'
• It is guaranteed that for each occurrence of '*', there will be a valid preceding element to match

Example 1:

Input:  s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more 'a', and "a*" matches "aa".

Example 2:

Input:  s = "ab", p = ".*"
Output: true
Explanation: ".*" matches any string.

Example 3:

Input:  s = "aab", p = "c*a*b"
Output: true
Explanation: 'c' is repeated 0 times, 'a' is repeated 2 times. "c*a*b" matches "aab".

Why This Problem Matters#

Regular Expression Matching (LC 10) is considered the hardest standard 2D DP string problem in the FAANG interview canon. Google, Meta, and Microsoft ask it at senior engineer level because it requires handling multiple overlapping cases for the * operator in a single recurrence — and getting the cases wrong produces plausible-looking but subtly incorrect solutions.

The core difficulty: * can match zero occurrences (skip the preceding char-star pair entirely) or one-or-more occurrences (consume a character and stay at the same pattern position). Managing both cases simultaneously in the DP recurrence requires careful state design that many candidates find non-intuitive.

Beyond the interview, this problem teaches you how regex engines actually work internally — a valuable insight for understanding NFA/DFA construction and string parsing algorithms.

The Core Insight#

Define dp[i][j] = True if s[:i] matches p[:j].

Base cases:

• dp[0][0] = True — empty string matches empty pattern.
• dp[i][0] = False for i > 0 — non-empty string cannot match empty pattern.
• dp[0][j]: empty string can match patterns like a*, a*b*, etc. (star pairs that match zero occurrences). Set dp[0][j] = dp[0][j-2] if p[j-1] == '*'.

Recurrence for dp[i][j] (i > 0, j > 0):

Case 1: p[j-1] is a regular character or .: Match the current character and check if the prefixes match:

dp[i][j] = dp[i-1][j-1] and (p[j-1] == s[i-1] or p[j-1] == '.')

Case 2: p[j-1] == '*': The star can match zero or more of p[j-2] (the preceding character).

• Zero occurrences: skip the x* pair entirely.

  Copy

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

• One or more occurrences: if p[j-2] matches s[i-1] (i.e., p[j-2] == s[i-1] or p[j-2] == '.'), then the star "consumed" one more character of s:

  Copy

  dp[i][j] |= dp[i-1][j]   (and p[j-2] matches s[i-1])

Full * case:

if p[j-1] == '*':
    dp[i][j] = dp[i][j-2]   # zero occurrences
    if p[j-2] == s[i-1] or p[j-2] == '.':
        dp[i][j] = dp[i][j] or dp[i-1][j]  # one+ occurrences

Answer: dp[len(s)][len(p)]

Building the DP Solution#

Step 1 — Recursive (exponential):

def isMatch(s, p):
    if not p: return not s
    first_match = bool(s) and p[0] in {s[0], '.'}
    if len(p) >= 2 and p[1] == '*':
        return isMatch(s, p[2:]) or (first_match and isMatch(s[1:], p))
    return first_match and isMatch(s[1:], p[1:])

Step 2 — Memoized recursion:

from functools import lru_cache
 
def isMatch(s, p):
    @lru_cache(None)
    def dp(i, j):
        if j == len(p): return i == len(s)
        first = i < len(s) and p[j] in {s[i], '.'}
        if j + 1 < len(p) and p[j + 1] == '*':
            return dp(i, j + 2) or (first and dp(i + 1, j))
        return first and dp(i + 1, j + 1)
    return dp(0, 0)

Step 3 — Bottom-up 2D tabulation: See Optimized Solution below.

Visual Dry Run#

Input: s = "aab", p = "c*a*b"

Key cells:

• dp[0][2]: p[1]='*' → zero occurrences: dp[0][0]=T → T
• dp[0][4]: p[3]='*' → zero occurrences: dp[0][2]=T → T
• dp[1][4]: p[3]='*'. Zero: dp[1][2]=F. One+: p[2]='a'==s[0]='a', so check dp[0][4]=T → T
• dp[2][4]: p[3]='*'. Zero: dp[2][2]=F. One+: p[2]='a'==s[1]='a', check dp[1][4]=T → T
• dp[3][5]: p[4]='b'==s[2]='b', check dp[2][4]=T → T

Optimized Solution#

Python#

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
 
        # dp[i][j] = True if s[:i] matches p[:j]
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True
 
        # Handle patterns that match empty string: a*, a*b*, etc.
        for j in range(2, n + 1):
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 2]  # zero occurrences of p[j-2]
 
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == '*':
                    # Zero occurrences: skip the 'x*' pair
                    dp[i][j] = dp[i][j - 2]
                    # One or more occurrences: p[j-2] must match s[i-1]
                    if p[j - 2] == s[i - 1] or p[j - 2] == '.':
                        dp[i][j] = dp[i][j] or dp[i - 1][j]
                elif p[j - 1] == s[i - 1] or p[j - 1] == '.':
                    # Direct match or wildcard '.'
                    dp[i][j] = dp[i - 1][j - 1]
                # else: characters don't match — dp[i][j] stays False
 
        return dp[m][n]

JavaScript#

var isMatch = function(s, p) {
    const m = s.length, n = p.length;
 
    const dp = Array.from({length: m + 1}, () => new Array(n + 1).fill(false));
    dp[0][0] = true;
 
    // Handle patterns matching empty string
    for (let j = 2; j <= n; j++) {
        if (p[j - 1] === '*') {
            dp[0][j] = dp[0][j - 2];
        }
    }
 
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (p[j - 1] === '*') {
                dp[i][j] = dp[i][j - 2];  // zero occurrences
                if (p[j - 2] === s[i - 1] || p[j - 2] === '.') {
                    dp[i][j] = dp[i][j] || dp[i - 1][j];  // one or more
                }
            } else if (p[j - 1] === s[i - 1] || p[j - 1] === '.') {
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }
 
    return dp[m][n];
};

Complexity Analysis#

Common Mistakes#

1. Forgetting to initialize dp[0][j] for star patterns. Patterns like a*, a*b* can match an empty string by using zero occurrences. dp[0][j] = dp[0][j-2] when p[j-1] == '*'. Missing this makes all patterns starting with stars incorrectly fail on empty strings.

2. Confusing "zero occurrences" and "one or more" for *. Zero occurrences: dp[i][j] = dp[i][j-2] (skip the char-star pair). One or more: dp[i][j] |= dp[i-1][j] when p[j-2] matches s[i-1]. Both cases must be checked. Many candidates only implement one.

3. Checking p[j-2] without ensuring j >= 2. When p[j-1] == '*' and j < 2, accessing p[j-2] is out of bounds. The constraint guarantees that * always has a preceding character, so j >= 2 is always true when p[j-1] == '*' in a valid pattern. But always verify this assumption.

4. Confusing LC 10 (regex *) with LC 44 (wildcard *). In LC 10, * means "zero or more of the PRECEDING character." In LC 44, * means "any sequence of any characters." The recurrences are completely different. Never mix them.

5. Using s[i] and p[j] (0-indexed) in a 1-indexed DP table. In the 1-indexed DP, s[i-1] is the i-th character of s, and p[j-1] is the j-th character of p. Off-by-one indexing is the most common source of silent bugs in this problem.

Interview Tips#

• Tackle the non-star case first: "Without *, the recurrence is simply: dp[i][j] = dp[i-1][j-1] and (s[i-1] == p[j-1] or p[j-1] == '.'). Then add * handling."
• Explain the * semantics clearly: "* means zero or more of the PRECEDING character — not the star itself. So a* represents the pair, not just a or just *."
• Walk through Example 3 aloud: s = "aab", p = "c*a*b". Show how c* disappears (zero matches), a* matches two 'a's, and 'b' matches 'b'.
• Compare to LC 44: "In Wildcard Matching (LC 44), * can match any sequence directly. Here, * modifies the preceding character — the table structure is the same, but the transitions differ."
• Mention memoized recursion as an alternative: "The recursive approach with @lru_cache is often easier to reason about during an interview, especially for the * cases."

Follow-up Questions#

Q: How does this differ from LC 44 Wildcard Matching? LC 44's * matches any sequence of characters directly. LC 10's * modifies the preceding character. In LC 44, the * transition is dp[i][j] = dp[i-1][j] or dp[i][j-1]. In LC 10, it is dp[i][j] = dp[i][j-2] or (match and dp[i-1][j]).

Q: What if the pattern can have consecutive stars like a**? The problem guarantees valid patterns — consecutive stars are not valid regex. In practice, this would need preprocessing to simplify a** to a*.

Q: How do real regex engines handle this? Real engines convert the pattern to an NFA (nondeterministic finite automaton) and simulate it. The DP approach is equivalent to NFA simulation but implemented as a table rather than state traversal. Both are O(m * n) for simple patterns.

Q: Can this be solved with a 1D rolling array? Yes, but it's tricky: dp[j-2] is used in the * case, so you need to be careful about the order of updates. Typically the 2D table is preferred in interviews for clarity.

Key Takeaways#

• dp[i][j] = True if s[:i] matches p[:j].
• Three cases: regular char match (diagonal), . match (diagonal), * (zero: j-2, one+: i-1 if preceding char matches).
• Initialize dp[0][j] = dp[0][j-2] when p[j-1] == '*' — this handles patterns like a*b*c* matching an empty string.
• The * in LC 10 modifies the PRECEDING character — fundamentally different from the * in LC 44 (wildcard matching).
• This is the hardest standard 2D DP string problem in FAANG interviews. Mastering it requires internalizing all three * cases and the empty-string initialization.
• Google and Meta use this problem specifically because the star's semantics are subtle and the recurrence is non-obvious — precisely what distinguishes strong candidates.