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

#leetcode #algorithms #python #dynamicprogramming

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

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]