10. Regular Expression Matching

Given a string s and a pattern p with . (any single char) and * (zero or more of the preceding), decide if p matches all of s. A classic 2D DP table over prefixes of both strings handles every case cleanly.

● Hard2D DPString DPPattern MatchingTypeScript

PROBLEM What we're solving

Return true if string s is fully matched by pattern p. Rules: . matches any single character; * matches zero or more copies of the character immediately before it. The entire string must be covered — not just a substring.

Concrete example: s="aab", p="c*a*b" → true. The c* matches zero cs, a* matches two as, and b matches the final b.

Another: s="aa", p="a" → false (pattern too short). s="aa", p="a*" → true.

KEY IDEA Build truth about prefixes bottom-up

Insight → Define dp[i][j] as "does s[0..i-1] match p[0..j-1]?". Because matching a prefix of s against a prefix of p only depends on smaller prefixes, we can fill the table left-to-right, top-to-bottom, and each cell is answered by at most two earlier cells. The * rule is the key branch: either skip the x* pair entirely (dp[i][j-2]), or — if the preceding char matches — extend by one more character ( dp[i-1][j]).

RECURRENCE Filling the DP table

0 · Base case. dp[0][0] = true (empty matches empty). For column 0 with j > 0: only patterns like a*, a*b* can match the empty string — set dp[0][j] = dp[0][j-2] whenever p[j-1] === '*'.
1 · Pattern char is *. Two sub-cases:
Zero uses: ignore the x* pair → dp[i][j] |= dp[i][j-2].
One-or-more uses: if the preceding pattern char (p[j-2]) is . or equals s[i-1], consume one more char of s → dp[i][j] |= dp[i-1][j].
2 · Pattern char is . or exact match. Direct consume: dp[i][j] = dp[i-1][j-1].
3 · Otherwise. Mismatch, no wildcard — leave dp[i][j] = false.

Classic confusion → The *"one or more" branch uses dp[i-1][j] (not dp[i-1][j-1] and not dp[i-1][j-2]). Staying at the same j is what lets *consume arbitrarily many characters — the pattern "stays" while s advances. Moving to j-1 or j-2 is the most common off-by-one mistake on this problem.

COST Complexity & alternatives

Recursive without memo

O(2^(m+n))

Exponential — each * branches in two directions repeatedly.

2D DP table

O(m·n)

O(m·n) time and space; rolling rows → O(n) space.

Space reduction: because each row only reads from the row above, you can keep just two rows at a time — prev and curr — cutting space from O(m·n) to O(n).

Pattern transfer → The same 2D "prefix vs prefix" DP table powers Wildcard Matching (LC 44, where * matches any sequence directly), Edit Distance (LC 72), Distinct Subsequences (LC 115), and Interleaving String (LC 97). Whenever you must reconcile two strings character-by-character with optional skips, reach for this shape.

RUN IT Fill the dp[i][j] matching table

s =p =

step 0 / 19

STARTBuild a (m+1)×(n+1) DP table. dp[i][j] = does s[0..2] match p[0..4]? All cells start false.

1function isMatch(s: string, p: string): boolean {
2  const m = s.length;
3  const n = p.length;
4 
5  // dp[i][j] = true if s[0..i-1] matches p[0..j-1]
6▶  const dp: boolean[][] = Array.from({ length: m + 1 }, () =>
7▶    new Array(n + 1).fill(false),
8▶  );
9  dp[0][0] = true; // empty string matches empty pattern
10 
11  // empty string can match "a*", "a*b*", etc.
12  for (let j = 2; j <= n; j++) {
13    if (p[j - 1] === '*') dp[0][j] = dp[0][j - 2];
14  }
15 
16  for (let i = 1; i <= m; i++) {
17    for (let j = 1; j <= n; j++) {
18      const sc = s[i - 1]; // current char of s
19      const pc = p[j - 1]; // current char of p
20 
21      if (pc === '*') {
22        // Case 1: zero occurrences of p[j-2] — skip the "x*" pair
23        dp[i][j] = dp[i][j - 2];
24 
25        // Case 2: one-or-more occurrences — p[j-2] must match sc
26        if (p[j - 2] === '.' || p[j - 2] === sc) {
27          dp[i][j] = dp[i][j] || dp[i - 1][j];
28        }
29      } else if (pc === '.' || pc === sc) {
30        // Direct match: '.' or exact char
31        dp[i][j] = dp[i - 1][j - 1];
32      }
33    }
34  }
35 
36  return dp[m][n];
37}

Loop state
i: —
j: —
sc (s[i-1]): '—'
pc (p[j-1]): '—'

current cell dp[i][j]source cell(s)chosen / final answer

slowfast

TYPESCRIPT The solution, annotated

isMatch.ts
function isMatch(s: string, p: string): boolean {
  const m = s.length;
  const n = p.length;

  // dp[i][j] = true if s[0..i-1] matches p[0..j-1]
  const dp: boolean[][] = Array.from({ length: m + 1 }, () =>
    new Array(n + 1).fill(false),
  );
  dp[0][0] = true; // empty string matches empty pattern

  // empty string can match "a*", "a*b*", etc.
  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++) {
      const sc = s[i - 1]; // current char of s
      const pc = p[j - 1]; // current char of p

      if (pc === '*') {
        // Case 1: zero occurrences of p[j-2] — skip the "x*" pair
        dp[i][j] = dp[i][j - 2];

        // Case 2: one-or-more occurrences — p[j-2] must match sc
        if (p[j - 2] === '.' || p[j - 2] === sc) {
          dp[i][j] = dp[i][j] || dp[i - 1][j];
        }
      } else if (pc === '.' || pc === sc) {
        // Direct match: '.' or exact char
        dp[i][j] = dp[i - 1][j - 1];
      }
    }
  }

  return dp[m][n];
}

Reading it block by block

Lines 5–6 — allocate the table. dp is an (m+1) × (n+1) boolean grid where index 0 represents the empty prefix. All cells start false.

Line 7 — base case dp[0][0]. An empty pattern matches an empty string. This seeds every subsequent derivation.

Lines 10–12 — seed the top row. A pattern like a*, a*b* can match the empty string by using zero of each quantified char. Only even-indexed columns (those ending in *) can be true here.

Lines 14–32 — fill the rest. For each (i,j) pair, look at the current pattern char p[j-1]. The *branch checks both the "zero occurrences" case (dp[i][j-2]) and the "one-or-more" case (dp[i-1][j], provided the preceding pattern char matches s[i-1]). The direct-match branch just propagates the diagonal.

Line 36 — answer. dp[m][n] asks: does all of s (length m) match all of p (length n)?

Complexity → O(m·n) time — we fill every cell of the table exactly once. O(m·n) space for the table; reducible to O(n) with a rolling two-row approach since each row only references the immediately preceding row.

INTERVIEWFollow-ups they'll ask

"Can you reduce space?" Yes — keep only prev and curr rows, cutting space from O(m·n) to O(n).
"Return all matching substrings, not just full match." Modify to not anchor at s[0] — start multiple DP paths from each index of s.
"How does this differ from Wildcard Matching (LC 44)?" In LC 44 the * matches any sequence by itself (not zero-or-more of the preceding char), so the DP has only one branch for *: dp[i][j] = dp[i-1][j] || dp[i][j-1].
"Recursive + memo approach?" Define match(i, j) with a 2D memo array. Same recurrence, same complexity — but top-down with early termination might be slightly faster in practice for sparse matches.
"Edge cases?" Empty s with pattern a*b* (should be true); pattern longer than string; consecutive * (invalid per constraints but worth naming).

OPTIMAL 2D DP

isMatch.ts
function isMatch(s: string, p: string): boolean {
  const m = s.length;
  const n = p.length;

  // dp[i][j] = true if s[0..i-1] matches p[0..j-1]
  const dp: boolean[][] = Array.from({ length: m + 1 }, () =>
    new Array(n + 1).fill(false),
  );
  dp[0][0] = true; // empty string matches empty pattern

  // empty string can match "a*", "a*b*", etc.
  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++) {
      const sc = s[i - 1]; // current char of s
      const pc = p[j - 1]; // current char of p

      if (pc === '*') {
        // Case 1: zero occurrences of p[j-2] — skip the "x*" pair
        dp[i][j] = dp[i][j - 2];

        // Case 2: one-or-more occurrences — p[j-2] must match sc
        if (p[j - 2] === '.' || p[j - 2] === sc) {
          dp[i][j] = dp[i][j] || dp[i - 1][j];
        }
      } else if (pc === '.' || pc === sc) {
        // Direct match: '.' or exact char
        dp[i][j] = dp[i - 1][j - 1];
      }
    }
  }

  return dp[m][n];
}

ALT 1 Top-down recursion + memo

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

Express the recurrence directly as match(i, j) and cache every (i, j) result so each state is solved once — same asymptotics as the table, but only the reachable states get computed.

approach-2.ts
function isMatch(s: string, p: string): boolean {
  const m = s.length;
  const n = p.length;

  // memo[i][j] caches the answer to match(i, j); null = not yet computed.
  const memo: (boolean | null)[][] = Array.from({ length: m + 1 }, () =>
    new Array<boolean | null>(n + 1).fill(null),
  );

  // Does s[i..] match p[j..]?
  function match(i: number, j: number): boolean {
    const cached = memo[i][j];
    if (cached !== null) return cached;

    let ans: boolean;
    if (j === n) {
      // Pattern exhausted: only a match if s is also exhausted.
      ans = i === m;
    } else {
      // Does the current single char of s match the current pattern char?
      const firstMatch = i < m && (p[j] === '.' || p[j] === s[i]);

      if (j + 1 < n && p[j + 1] === '*') {
        // 'x*' => either skip the pair (zero occurrences), or, if the
        // current char matches, consume one char of s and stay on the pair.
        ans = match(i, j + 2) || (firstMatch && match(i + 1, j));
      } else {
        // Ordinary char or '.': both sides must advance by one.
        ans = firstMatch && match(i + 1, j + 1);
      }
    }

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

  return match(0, 0);
}

Note → Indexing here is forward (s[i..] vs p[j..]) rather than the table's prefix indexing, but the two * branches are identical: match(i, j + 2) is "zero occurrences" and match(i + 1, j)is "one or more." The cache turns the otherwise-exponential tree into O(m·n) distinct states.

ALT 2 Plain recursion (no memo)

O(2^(m+n)) time · O(m + n) stack space

The exact same branching with the cache removed — correct, but the overlapping * sub-calls are recomputed exponentially. This is the baseline that motivates memoization and the DP table.

approach-3.ts
function isMatch(s: string, p: string): boolean {
  const m = s.length;
  const n = p.length;

  // Does s[i..] match p[j..]?  No caching — every call recomputes from scratch.
  function match(i: number, j: number): boolean {
    if (j === n) {
      // Pattern exhausted: match only if s is exhausted too.
      return i === m;
    }

    // Does the current single char of s match the current pattern char?
    const firstMatch = i < m && (p[j] === '.' || p[j] === s[i]);

    if (j + 1 < n && p[j + 1] === '*') {
      // 'x*' => skip the pair (zero occurrences), OR consume one matching
      // char of s and stay on the pair (one or more occurrences).
      return match(i, j + 2) || (firstMatch && match(i + 1, j));
    }

    // Ordinary char or '.': advance both sides by one.
    return firstMatch && match(i + 1, j + 1);
  }

  return match(0, 0);
}

Note → Drop the memo and the branching is unchanged — proof that the only thing memoization adds is reuse. On inputs with many * quantifiers (e.g. s="aaaaaaaaaa", p="a*a*a*a*b") this blows up to exponential time; add the cache and it collapses back to O(m·n).

MNEMONIC The one-liner

"* either skips its pair (dp[i][j-2]) or consumes one more from s while staying at j (dp[i-1][j])."

TRIGGERS When you see _ → reach for _

"does the entire string match a regex-like pattern"	2D DP over s and p prefixes
"pattern has . and * wildcards, full-string match"	dp[i][j] = does s[0..i-1] match p[0..j-1]
"zero or more of preceding char" (Kleene star)	two branches: dp[i][j-2] (zero) or dp[i-1][j] (more)
"related: Wildcard Matching, Edit Distance"	same two-string prefix DP shape

SKELETON The reusable shape

skeleton.ts
const m = s.length, n = p.length;
const dp: boolean[][] = Array.from({ length: m + 1 }, () =>
  new Array(n + 1).fill(false));
dp[0][0] = true;
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] === '.' || p[j-2] === s[i-1])
        dp[i][j] = dp[i][j] || dp[i-1][j]; // one+ occurrences
    } else if (p[j-1] === '.' || p[j-1] === s[i-1]) {
      dp[i][j] = dp[i-1][j-1]; // direct match
    }
  }
}
return dp[m][n];

FLASHCARDS Tap to flip

What does dp[i][j] represent?

true if s[0..i-1] (first i chars) is fully matched by p[0..j-1] (first j chars).

tap to flip

1 / 8

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What is the time complexity of the 2D DP solution for isMatch(s, p)?

QUESTION 02

When p[j-1] === '*', which cell provides the "zero occurrences" case?

QUESTION 03

When p[j-1] === '*' and the preceding char matches s[i-1], which cell provides the "one or more" case?

QUESTION 04

Trace: s="aab", p="c*a*b". What does isMatch return?

QUESTION 05

Why can dp[0][j] be true for some j > 0?

QUESTION 06

s="ab", p=".*". Result?

QUESTION 07

How would you reduce space from O(m·n) to O(n)?

QUESTION 08

#10 · Regular Expression Matching2D DP dp[i][j] = does p[j:] match s[i:]. A "*" quantifier can match zero occurrences (skip two pattern chars) or one-plus more (current chars match and stay at dp[i+1][j]). A "." matches any single character.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Build truth about prefixes bottom-up

RECURRENCE Filling the DP table

COST Complexity & alternatives

RUN IT Fill the dp[i][j] matching table

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL 2D DP

ALT 1 Top-down recursion + memo

ALT 2 Plain recursion (no memo)

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _