💬 Discord
Sign In
NeetCode #743LC-10Hard2-D Dynamic ProgrammingNC 150NC 250
← Back to All Problems

#743 · #10 · Regular Expression Matching(正则表达式匹配)

📌 Problem Statement & Constraints

Given an input string s and a pattern p supporting . (any single character) and * (zero or more of the preceding element), return whether the pattern matches the entire string. Constraints: 1 <= s.length <= 20, 1 <= p.length <= 20, s is lowercase letters, and p is lowercase letters, ., and *.

💡 Core Algorithmic Approaches

  1. dp[i][j] is true when s[0..i-1] matches p[0..j-1].
  2. A plain character or . matches exactly one character, so dp[i][j] = dp[i-1][j-1] when it matches.
  3. When p[j-1] is *, the group x* either matches zero characters (dp[i][j-2]) or one more character of s when x matches s[i-1] (dp[i-1][j]).
  4. Using dp[i-1][j] rather than dp[i-1][j-2] is what lets the star repeat arbitrarily.

💻 Benchmark Python3 Implementation

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True
        for j in range(1, n + 1):
            if p[j - 1] == "*":        # "x*" can match the empty string
                dp[0][j] = dp[0][j - 2]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == "*":
                    # zero occurrences, or one more matched by p[j-2]
                    dp[i][j] = dp[i][j - 2]
                    if p[j - 2] == "." or p[j - 2] == s[i - 1]:
                        dp[i][j] = dp[i][j] or dp[i - 1][j]
                elif p[j - 1] == "." or p[j - 1] == s[i - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
        return dp[m][n]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n): one state per pair of prefixes with O(1) work each.
💾 Space Complexity
O(m * n): the DP table.

⚠️ Interview Pitfalls & Follow-ups

  • Using dp[i-1][j-2] for repetition: the correct repeat term is dp[i-1][j], which stays on the same pattern position and consumes one character.
  • Omitting the first-row initialisation for stars: a* or a*b* can match the empty string, so dp[0][j] needs setting.
  • Treating . as matching zero characters: . matches exactly one.
  • Indexing p[j-2] when j == 1: a * cannot begin a valid pattern, which is what makes that index safe.