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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Regular Expression Matching

Number: 10

Difficulty: Hard

Paid? No

Companies: Amazon, Bloomberg, Google, Meta, TikTok, Zoho, Microsoft, Snowflake, Apple, ByteDance, Citadel, Coupang, Turing, Adobe, Uber, Yahoo, Oracle, Confluent, Luxoft, X, Airbnb

Problem Description

Given an input string s and a pattern p, implement regular expression matching with support for '.' (matches any single character) and '*' (matches zero or more of the preceding element). The matching should cover the entire input string.

Key Insights

  • Use recursion or dynamic programming to simulate matching as the '*' operator can affect the current and following characters.
  • The '.' operator is a wildcard that matches any single character.
  • When encountering a '*' in the pattern, consider both skipping the preceding element or consuming one character from the string if it matches.
  • Using memoization helps to save intermediate results and efficiently process overlapping subproblems.

Space and Time Complexity

Time Complexity: O(mn) where m = length(s) and n = length(p), due to exploring each subproblem combination. Space Complexity: O(mn) for storing the memoization table in the dynamic programming or recursive approach.

Solution

The solution uses a top-down recursive strategy with memoization to efficiently match the string against the pattern. For each character position in s and p, we check if they match directly or if the pattern character is '.' to allow any match. When encountering '' in the pattern, two possibilities are explored: either the '' stands for zero occurrences of the preceding element, or if there is a valid match, it accounts for one occurrence and we proceed further in the string while maintaining the same pattern index. The memoization aspect prevents repeated computations of the same (i, j) state in the recursion, resulting in an improved overall runtime.

Code Solutions

# Python solution using recursion with memoization
def isMatch(s: str, p: str) -> bool:
    memo = {}

    def dp(i: int, j: int) -> bool:
        # If result is already computed, return it.
        if (i, j) in memo:
            return memo[(i, j)]

        # If we have reached the end of the pattern, s must also be at the end.
        if j == len(p):
            ans = i == len(s)
        else:
            # Check if current characters match
            first_match = i < len(s) and (p[j] == s[i] or p[j] == '.')
            
            # If there is a '*' coming after the current pattern character    
            if j + 1 < len(p) and p[j+1] == '*':
                # Two cases:
                # 1. '*' stands for zero occurrence -> skip current pattern char and '*'
                # 2. first_match is true, so we try to consume one character in s and remain at same pattern index
                ans = dp(i, j+2) or (first_match and dp(i+1, j))
            else:
                # No '*' means we directly check next characters in both s and p.
                ans = first_match and dp(i+1, j+1)
        
        memo[(i, j)] = ans
        return ans

    return dp(0, 0)


# Example test run
#print(isMatch("aa", "a*"))  # Expected output: True
← Back to All Questions