Hard#109 min readDynamic Programming2D DPStringsLeetCode

Regular Expression Matching

Bottom-up 2D DP with star two-branch transition

2D DP on string vs pattern. The ‘*’ case has two transitions. Think carefully.

Published Apr 17, 2026

Problem

Implement regex matching with support for . and *:

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

Return true iff the pattern matches the entire input string.

Input

Output

false

Explanation

"a" matches one "a", not two.

Input

Output

true

Explanation

"a*" matches zero or more "a".

Input

Output

true

Explanation

".*" matches any sequence.

Input

Output

true

Explanation

"c*" matches zero "c", "a*" matches "aa", then "b" matches "b".

Intuition

Define dp[i][j] as "does p[..j] match s[..i]?" We're asking dp[m][n].

Work through the last character of p[..j] (index j - 1):

Case 1 — p[j-1] is a literal char or .. Then p[..j] consumes one character of s. The match requires that character to be a single-char match, and p[..j-1] to have matched everything before:

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

Case 2 — p[j-1] is *. Now * binds to p[j-2] (the character it modifies). The combined unit p[j-2]* can match zero or more copies. Two branches:

Zero copies — skip the whole p[j-2]* pair: dp[i][j] = dp[i][j-2].
One or more copies — if p[j-2] can eat s[i-1] (either . or same char), then consuming one copy reduces to matching the same pattern against s[..i-1]: dp[i][j] |= dp[i-1][j].

Either succeeding is enough; take the OR.

Base: dp[0][0] = true (empty matches empty). Crucially, dp[0][j] for pure x*x*x*... is true — any sequence of star-pairs can match the empty string. Seed that by dp[0][j] = p[j-1] == '*' && dp[0][j-2].

The "zero copies" branch is the one everyone forgets. It's what lets "c*a*b" match "aab" — the c* consumes zero characters and is dropped entirely.

Approach

Memoized Recursion

TimeO(m · n)

SpaceO(m · n)

Recurse on (i, j) representing "do p[i..] and s[j..] match?" At each call, check if the next pattern character is followed by *. If yes, branch on zero-use (skip two pattern chars) or consume (if the current char matches). Memoize to avoid repeated subproblems.

Equivalent to the DP but often read more easily because the zero/one-or-more split is explicit in the control flow.

impl Solution {
    pub fn is_match(s: String, p: String) -> bool {
        let s = s.as_bytes();
        let p = p.as_bytes();
        let mut memo: Vec<Vec<Option<bool>>> = vec![vec![None; p.len() + 1]; s.len() + 1];
        fn go(
            i: usize,
            j: usize,
            s: &[u8],
            p: &[u8],
            memo: &mut Vec<Vec<Option<bool>>>,
        ) -> bool {
            if let Some(v) = memo[i][j] {
                return v;
            }
            let ans = if j == p.len() {
                i == s.len()
            } else {
                let first = i < s.len() && (p[j]= b'.' || p[j]= s[i]);
                if j + 1 < p.len() && p[j + 1]= b'*' {
                    // Zero copies, or one-more-copy + same pattern.
                    go(i, j + 2, s, p, memo) || (first && go(i + 1, j, s, p, memo))
                } else {
                    first && go(i + 1, j + 1, s, p, memo)
                }
            };
            memo[i][j]= Some(ans);
            ans
        }
        go(0, 0, s, p, &mut memo)
    }
}

Rust · runnable

function isMatch(s: string, p: string): boolean {
  const memo = new Map<number, boolean>();
  const key = (i: number, j: number) => i * (p.length + 1) + j;
  const go = (i: number, j: number): boolean => {
    const k = key(i, j);
    const cached = memo.get(k);
    if (cached !== undefined) return cached;
    let ans: boolean;
    if (j === p.length) {
      ans = i === s.length;
    } else {
      const first = i < s.length && (p[j]= '.' || p[j]= s[i]);
      if (j + 1 < p.length && p[j + 1]= '*') {
        ans= go(i, j + 2) || (first && go(i + 1, j));
      } else {
        ans= first && go(i + 1, j + 1);
      }
    }
    memo.set(k, ans);
    return ans;
  };
  return go(0, 0);
}

TypeScript · runnable

Bottom-Up 2D DP

TimeO(m · n)

SpaceO(m · n)

Recommended

Fill dp[0..=m][0..=n] forward. The star-pair seed for dp[0][j] is the one subtle detail — do it in the initialization pass before the main loop.

impl Solution {
    pub fn is_match(s: String, p: String) -> bool {
        let s = s.as_bytes();
        let p = p.as_bytes();
        let m = s.len();
        let n = p.len();
        let mut dp = vec![vec![false; n + 1]; m + 1];
        dp[0][0] = true;
        // Star-pair prefixes (e.g. "a*b*c*") can match the empty string.
        for j in 2..=n {
            if p[j - 1] == b'*' {
                dp[0][j] = dp[0][j - 2];
            }
        }
        for i in 1..=m {
            for j in 1..=n {
                if p[j - 1] == b'*' {
                    // Zero copies: drop the x* pair.
                    dp[i][j] = dp[i][j - 2];
                    // One or more copies: current char must match p[j-2].
                    if p[j - 2] == b'.' || p[j - 2] == s[i - 1] {
                        dp[i][j] |= dp[i - 1][j];
                    }
                } else if p[j - 1] == b'.' || p[j - 1] == s[i - 1] {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        dp[m][n]
    }
}

Rust · runnable

function isMatch(s: string, p: string): boolean {
  const m = s.length;
  const n = p.length;
  const dp: boolean[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(false));
  dp[0][0] = true;
  // Star-pair prefixes (e.g. "a*b*c*") can match the 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];
        if (p[j - 2] === '.' || p[j - 2] === s[i - 1]) {
          dp[i][j] = dp[i][j] || dp[i - 1][j];
        }
      } else if (p[j - 1] === '.' || p[j - 1] === s[i - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      }
    }
  }
  return dp[m][n];
}

TypeScript · runnable

Trace

2D fill on s = "aab", p = "c*a*b" (columns are p prefixes):

i (s[i-1])	''	c	c*	c*a	ca	cab
0 ''	T	F	T	F	T	F
1 'a'	F	F	F	T	T	F
2 'a'	F	F	F	F	T	F
3 'b'	F	F	F	F	F	T

Return dp[3][5] = true. ✓ The c* lets the empty string through; a* eats both as; b matches b.

Edge cases

Empty pattern, non-empty string — false. No pattern consumes characters.
Empty string — only patterns of form (x*)+ match. The star-pair seed handles this.
.* — matches any string. The star branch's "one or more" with . (which matches any char) keeps the state alive; the "zero copies" handles empty.
Star at index 0 — problem constraints guarantee * always follows a char, so we don't have to handle "*..." as the entire pattern.
Leading * behavior — not in LC's regex; * always binds to exactly one prior character.

ℹ️

Note

The "zero copies" branch is the whole problem. Without it, "c*a*b" couldn't match "aab" (the c* segment would have no way to consume zero characters). Whenever you write regex or glob matching by hand, the "ignore the star pair entirely" case is the one to audit first.

Takeaway

Regex matching is the first DP on this roadmap where the transition has two possible branches from one state. That's why it's Hard: you have to correctly OR two recursive calls in the star case, and miss-handling dp[0][j] gives wrong answers only on tricky inputs.

The pattern generalizes: any problem where a single "command character" can consume zero or more input symbols needs the two-branch transition plus the empty-input seed. #44 Wildcard Matching uses the same template with * meaning "any sequence of any chars" (simpler than #10 in some ways, because the star is unbound from a preceding character).

The DP itself is a disciplined rewrite of the memoized recursion — once the recursion is clear, the table is mechanical.

Medium#72

Edit Distance

dp[i][j] = min edits for s1[0..i] → s2[0..j]. Three transitions: insert, delete, replace.

Medium#1143

Longest Common Subsequence

The classic 2D string DP. Understand match vs. skip transitions.