We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Regular Expression Matching

Difficulty: Hard

Problem Description

Given an input string s and a pattern p, implement regular expression matching with support for . and * where:

  • . Matches any single character.
  • * Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Key Insights

  • The . character can represent any character, providing flexibility in matching.
  • The * character allows for matching zero or more occurrences of the previous character, which can significantly affect the matching process.
  • The problem can be approached using dynamic programming or recursion with memoization due to overlapping subproblems.

Space and Time Complexity

Time Complexity: O(m * n), where m is the length of the string and n is the length of the pattern. Space Complexity: O(m * n) for the dynamic programming table, or O(m + n) for the recursive approach with memoization.

Solution

To solve this problem, we can use a dynamic programming approach. We create a 2D table (dp) where dp[i][j] indicates whether the first i characters of the string s match the first j characters of the pattern p. The algorithm follows these steps:

  1. Initialize the dp table with dimensions (m+1) x (n+1) where m and n are the lengths of s and p.
  2. Base case: An empty pattern matches an empty string.
  3. Fill in the dp table using the rules defined by . and *.
  4. Return the value in dp[m][n], which indicates if the entire string matches the entire pattern.

Code Solutions

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

    # Handle patterns with '*' at the start
    for j in range(1, n + 1):
        if p[j - 1] == '*':
            dp[0][j] = dp[0][j - 2]

    # Fill the dp table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == '.' or p[j - 1] == s[i - 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]
← Back to All Questions