10. Regular Expression Matching

At a Glance

Topic: dp-2d
Pattern: Dynamic Programming — string vs pattern (with * Kleene on prior atom)
Difficulty: Hard
Companies: Google, Facebook, Microsoft, Amazon, Apple
Frequency: High
LeetCode: 10

Problem (one-liner)

Given input text and pattern p with . (any one char) and * (zero or more of the preceding element), return whether the full string matches the pattern.

Recognition Cues

Pattern with star on previous char, not on subpattern
True matching = consider take / skip for *
Overlapping subproblems on (textIndex, patternIndex) — 2D boolean DP

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Backtracking with memo — O(TP) states (can be good).
Bottom-up DP match[textIndex][patternIndex] — O(len(text) * len(p)) time and space, space-optimizable — optimal asymptotically.

Optimal Solution

Go

func isMatch(text string, pattern string) bool {
	textLen := len(text)
	patternLen := len(pattern)
	// match[textIndex][patternIndex] = first patternIndex chars match first textIndex chars
	match := make([][]bool, textLen+1)
	for row := range match {
		match[row] = make([]bool, patternLen+1)
	}
	match[0][0] = true
	for patternIndex := 1; patternIndex <= patternLen; patternIndex++ {
		if pattern[patternIndex-1] == '*' {
			// zero copies of char before *
			match[0][patternIndex] = match[0][patternIndex-2]
		}
	}
	for textIndex := 1; textIndex <= textLen; textIndex++ {
		for patternIndex := 1; patternIndex <= patternLen; patternIndex++ {
			current := pattern[patternIndex-1]
			if current == '.' || current == text[textIndex-1] {
				match[textIndex][patternIndex] = match[textIndex-1][patternIndex-1]
			} else if current == '*' {
				// zero of preceding
				match[textIndex][patternIndex] = match[textIndex][patternIndex-2]
				preceding := pattern[patternIndex-2]
				if preceding == '.' || preceding == text[textIndex-1] {
					// one or more: carry from same text prefix with pattern unchanged
					match[textIndex][patternIndex] = match[textIndex][patternIndex] || match[textIndex-1][patternIndex]
				}
			}
		}
	}
	return match[textLen][patternLen]
}

JavaScript

function isMatch(text, pattern) {
  const textLen = text.length;
  const patternLen = pattern.length;
  const match = Array.from({ length: textLen + 1 }, () =>
    new Array(patternLen + 1).fill(false)
  );
  match[0][0] = true;
  for (let patternIndex = 1; patternIndex <= patternLen; patternIndex += 1) {
    if (pattern[patternIndex - 1] === '*') {
      match[0][patternIndex] = match[0][patternIndex - 2];
    }
  }
  for (let textIndex = 1; textIndex <= textLen; textIndex += 1) {
    for (let patternIndex = 1; patternIndex <= patternLen; patternIndex += 1) {
      const current = pattern[patternIndex - 1];
      if (current === '.' || current === text[textIndex - 1]) {
        match[textIndex][patternIndex] = match[textIndex - 1][patternIndex - 1];
      } else if (current === '*') {
        match[textIndex][patternIndex] = match[textIndex][patternIndex - 2];
        const preceding = pattern[patternIndex - 2];
        if (preceding === '.' || preceding === text[textIndex - 1]) {
          match[textIndex][patternIndex] =
            match[textIndex][patternIndex] || match[textIndex - 1][patternIndex];
        }
      }
    }
  }
  return match[textLen][patternLen];
}

Walkthrough

text = "aa", pattern = "a*". * lets zero or more a; two as match.

Invariant: match[textIndex][patternIndex] considers only prefixes; * always has a defined preceding char in valid patterns.

Edge Cases

Empty text — can match "" with patterns like a* or .*
* at position 0 — invalid in LeetCode constraints (well-formed patterns)

Pitfalls

* meaning — applies to directly preceding pattern char only
Confusing with wildcard substring * (different problem)

Variants

44. Wildcard Matching (? and *) — different * semantics; often solved with greedy + backtrack or DP
Count matches — sum DP instead of OR
Multiple patterns / NFA — graph of states

Mind-Map Tags

#regex-dp #kleene-star #dot-wildcard #prefix-match #boolean-table