4.24.11 — Regular Expression Matching

LeetCode 10 · Hard

The problem

Implement matching for two special characters:

• . matches any single character.
• * matches zero or more of the character before it.

The match must cover the entire string, not just part of it.

s = "aa",    p = "a"      →  false   (p matches only one a)
s = "aa",    p = "a*"     →  true    (a* is two a's)
s = "ab",    p = ".*"     →  true    (.* is any sequence)
s = "aab",   p = "c*a*b"  →  true    (c* is zero c's)

Constraints:

• 1 <= s.length <= 20
• 1 <= p.length <= 20
• s contains only lowercase English letters.
• p contains lowercase English letters, ., and *.
• It is guaranteed for each appearance of the character *, there will be a previous valid character to match.

Plain-English Restatement: You are writing a mini regular expression engine. You need to check if a target string s exactly fits a pattern p. The pattern has literal characters (like 'a'), a wildcard . that acts like a blank tile in Scrabble (can be any letter), and a multiplier * that says "take the preceding character and repeat it as many times as you want, including zero times."

Brute Force Approach: You can write a recursive function that checks the first character. If it encounters a *, it branches: one branch tries repeating the character 0 times, another tries 1 time, another 2 times, etc.

• Time Complexity: Exponential, roughly O(2^{m+n}). Every * acts like a massive fork in the road of the recursion tree.
• Why it's wasteful: If the pattern is a*b*c and string is aabbc, deciding how many as to consume is independent of how many bs to consume. The brute force approach re-evaluates the b*c portion for every incorrect guess of a*. DP caches whether a specific suffix of s matches a specific suffix of p.

The pattern

Two strings, so a grid. dp[i][j] is true when the first i characters of s match the first j characters of p.

* is the only difficulty. Everything else is a character comparison.

Read the pattern in pairs: a * always attaches to the character before it, so "a*" is one unit, not two. When p[j-1] is *, the unit is p[j-2] followed by *, and it can be used two ways:

Zero occurrences. Throw the whole unit away and match s against the pattern with those two characters removed:

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

One or more occurrences. Only possible if p[j-2] matches s[i-1]. Then consume that one character of s and keep the pattern unit available for more:

dp[i][j] = dp[i-1][j]

Either works, so they are joined by or.

Note dp[i-1][j], not dp[i-1][j-2]. The j does not move, because * can match again. That single index is the difference between a* matching one a and matching many, and it is the line to get right.

When p[j-1] is not a *, it is a plain comparison:

dp[i][j] = dp[i-1][j-1] \ \text{if}\ p[j-1] = s[i-1] \ \text{or}\ p[j-1] = \text{'.'}

The base cases

dp[0][0] = True — two empty strings match.

dp[0][j] — can a non-empty pattern match the empty string? Only if it is entirely made of x* units. So for each * at position j-1, dp[0][j] = dp[0][j-2].

That is the base case people forget, and it is what makes "c*a*b" fail correctly against "" while "c*a*" succeeds.

dp[i][0] = False for i > 0 — an empty pattern matches nothing.

The solution

Python

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True

        for j in range(1, n + 1):                       # empty s against a pattern
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 2]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                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 or more
                elif p[j - 1] == s[i - 1] or p[j - 1] == '.':
                    dp[i][j] = dp[i - 1][j - 1]

        return dp[m][n]

TypeScript

function isMatch(s: string, p: string): boolean {
  const m = s.length, n = p.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(false));
  dp[0][0] = true;

  for (let j = 1; 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];
        if (p[j - 2] === s[i - 1] || p[j - 2] === '.') {
          dp[i][j] = dp[i][j] || dp[i - 1][j];
        }
      } else if (p[j - 1] === s[i - 1] || p[j - 1] === '.') {
        dp[i][j] = dp[i - 1][j - 1];
      }
    }
  }

  return dp[m][n];
}

dp[i][j-2] is always the first thing tried in the * case, because zero occurrences is always allowed regardless of what s holds.

dp[i-1][j] keeps j fixed, which is what lets a* consume several characters, one per step.

p[j-2] is safe to index whenever p[j-1] is *, because a valid pattern never starts with *. The problem guarantees this; in production code you would validate it.

Trace

s = "aab", p = "c*a*b".

dp[0][2] is true because c* can be zero cs. dp[0][4] is true because a* can also be zero. Then dp[1][4] and dp[2][4] become true as a* absorbs one and then two as — each time via dp[i-1][j] with j unchanged. Finally b matches b and dp[3][5] is true ✓.

Complexity

O(mn) time and space.

Code Walkthrough

1. Grid Init: dp = [[False] * (n + 1) for _ in range(m + 1)].
2. Base Case 1: dp[0][0] = True. Empty pattern matches empty string.
3. Base Case 2 (Empty String vs Pattern): We loop over the pattern. If we see a *, we look two steps back: dp[0][j] = dp[0][j-2]. This correctly identifies that "a*b*" can match "" because each * can mean "zero occurrences".
4. Main Loop: We iterate i from 1 to m and j from 1 to n.
5. The * Logic: If p[j-1] == '*':
   • First, we say dp[i][j] = dp[i][j-2]. This means "Assume 0 occurrences. If the pattern without this x* unit matched the current string, we're good."
   • Then, if p[j-2] == s[i-1] or p[j-2] == '.': we check if the preceding character actually matches the current character in the string. If it does, we can consume it: dp[i][j] = dp[i][j] or dp[i-1][j]. The dp[i-1][j] asks "Did the remainder of the string match this exact same pattern?", which allows multiple characters to be consumed.
6. The Normal Logic: elif p[j-1] == s[i-1] or p[j-1] == '.': Just check if the characters match (or if the pattern is .). If so, inherit the validity from dp[i-1][j-1].

Complexity Derivation

• Time Complexity: O(m \times n). The 2D table has (m+1) \times (n+1) cells. For each cell, we do at most a constant O(1) number of character comparisons and boolean lookups.
• Space Complexity: O(m \times n) to store the DP table. Like other 2D DPs, it can be optimized to O(n) by keeping only the current and previous rows, though the code gets slightly harder to read.

Edge Cases

• Pattern empty: If p = "", s = "a", it fails correctly.
• Pattern .*: A dot followed by a star matches literally anything. The logic handles it flawlessly because p[j-2] == '.' is always true, letting it consume characters endlessly via dp[i-1][j].

The naive recursive matcher without memoisation is exponential — ".*.*.*.*b" against a long string of as is the classic timeout input, and it is the same shape as the catastrophic backtracking that causes ReDoS attacks in real regex engines. Chapter 8 covers that; mentioning it here is a good connection.

The wildcard cousin

Wildcard Matching (LeetCode 44) uses ? for any single character and * for any sequence, unattached to a preceding character. It is genuinely easier, because * stands alone:

dp[i][j] = dp[i][j-1] \ \text{(star matches empty)} \ \text{or}\ dp[i-1][j] \ \text{(star absorbs one more)}

Do not mix the two up. In this problem * modifies the previous character; in wildcard matching it does not. That difference changes the recurrence completely, and interviewers sometimes switch between them to see whether you noticed.

Where this goes next

• Wildcard Matching — above.
• A real regex engine — compiles the pattern to an NFA and simulates it, which runs in O(mn) guaranteed with no backtracking. Thompson's construction is the classic method, and it is why some engines are immune to ReDoS while backtracking engines are not.
• Interleaving String, Edit Distance — the same two-string grid.

What the interviewer will push on

"How do you handle *?" Two cases joined by or — zero occurrences via dp[i][j-2], one or more via dp[i-1][j].

"Why does j stay the same in the one-or-more case?" So * remains available to match again.

"What is dp[0][j] for?" A pattern of only x* units can match the empty string. Forgetting it breaks "c*a*b" handling.

"How is this different from wildcard *?" Here * modifies the previous character; there it stands alone.

"Why is the naive recursion exponential?" Each * branches, and the same states are recomputed. Then name ReDoS.

"How does a real regex engine avoid this?" NFA simulation, linear and backtracking-free.

One thing to volunteer: say that you read the pattern in pairs — x* is one unit — before writing anything. Almost every wrong solution to this problem treats * as an independent character.

Next: 4.25 covers the family where you do not need to consider every option at all, and the exchange argument that tells you whether greed is safe.