# LeetCode 10: Regular Expression Matching — Step-by-Step Visual Trace

**Hard** — Dynamic Programming | String | Recursion

## The Problem

Given a string s and a pattern p, implement regular expression matching with support for '.' and '*' where '.' matches any single character and '*' matches zero or more of the preceding element.

## Approach

Use dynamic programming with a 2D table where dp[i][j] represents whether the first i characters of string s match the first j characters of pattern p. Handle base cases for empty strings and patterns with '*', then fill the table by checking character matches, wildcard dots, and star repetitions.

**Time:** O(m*n) · **Space:** O(m*n)

## Code

```python
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)

        # Create a 2D table dp to store whether s[:i] matches p[:j].
        dp = [[False] * (n + 1) for _ in range(m + 1)]

        # Base case: empty string matches empty pattern.
        dp[0][0] = True

        # Fill the first row of dp based on '*' in the pattern.
        for j in range(2, n + 1):
            if p[j - 1] == "*":
                dp[0][j] = dp[0][j - 2]

        # Fill the dp table based on characters in s and p.
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == s[i - 1] or p[j - 1] == ".":
                    dp[i][j] = dp[i - 1][j - 1]
                elif p[j - 1] == "*":
                    dp[i][j] = dp[i][j - 2] or (
                        dp[i - 1][j] and (s[i - 1] == p[j - 2] or p[j - 2] == ".")
                    )

        return dp[m][n]
```

## Watch It Run

> **[Open interactive visualization](https://tracelit.dev/app?trace=0010_regular-expression-matching)**

> **Try it yourself:** Open [TraceLit](https://tracelit.dev/app?trace=0010_regular-expression-matching) and step through every line.

---

*Built with [TraceLit](https://tracelit.dev) — the visual algorithm tracer for LeetCode practice.*