Regular Expression Matching

PracticeNeetCode ↗LeetCode ↗

Given a string s and a pattern p where . matches any single character and * matches zero or more of the element immediately before it, determine whether p matches the entire string s.

Example

Key Pointers

• A * always pairs with the character right before it, and it offers two independent options: skip that pair entirely (zero occurrences), or consume one matching character from s and stay on the same spot in p (one more occurrence).
• Building the table from the end of both strings backward makes "what's left to match" a clean recursive shrinking problem.
• . always counts as a match against any single character, so matching logic needs to check for it alongside exact character equality.

Step-by-Step Analysis

1. Build a boolean grid sized (len(s)+1) × (len(p)+1), with the bottom-right corner (both strings fully consumed) set to True.
2. Fill from the bottom-right corner upward and leftward.
3. At each cell, compute whether the current characters of s and p match directly (accounting for .).
4. If the next pattern character is *, the cell is True if either skipping the x* pair works, or the current characters match and consuming one from s (staying on the same pattern position) works.
5. Otherwise, the cell is True only if the current characters match and the diagonal (both advance by one) is True.
6. The top-left cell holds the answer for the full strings.

Complexity

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

Code

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

    for i in range(m, -1, -1):
        for j in range(n - 1, -1, -1):
            first_match = i < m and p[j] in (s[i], ".")

            if j + 1 < n and p[j + 1] == "*":
                dp[i][j] = dp[i][j + 2] or (first_match and dp[i + 1][j])
            else:
                dp[i][j] = first_match and dp[i + 1][j + 1]

    return dp[0][0]

Code Explanation

How the solution above works, piece by piece.

1. dp[i][j] = does s[i:] match p[j:]? Two empty suffixes match: dp[m][n] = True.
2. first_match: s[i] exists and equals p[j] or p[j] is ..
3. If p[j+1] is *: either use zero copies (skip two pattern characters, dp[i][j+2]) or, if the first character matches, consume it and keep the same pattern (dp[i+1][j]).
4. Otherwise the first characters must match and both advance: dp[i+1][j+1].
5. Filling from the ends backwards means every needed cell is ready. O(m × n) time and space.

Visual Walkthrough

Running it on s = "aa", p = "a*":

Video Explanation

NeetCode — Dynamic Programming Top-Down Memoization, LeetCode 10