Regular Expression Matching

Difficulty: Hard | Acceptance: 29.56% | Paid: No

Topics: String, Dynamic Programming, Recursion

• Examples
• Constraints
• Brute Force Recursion
• Top-Down Memoization
• Bottom-Up Dynamic Programming

Examples

Input

s = "aa", p = "a"

Output

false

Explanation

”a” does not match the entire string “aa”.

Input

s = "aa", p = "a*"

Output

true

Explanation

’*’ means zero or more of the preceding element, ‘a’. Therefore, by repeating ‘a’ once, it becomes “aa”.

Input

s = "ab", p = ".*"

Output

true

Explanation

”.” means “zero or more () of any character (.)“.

Constraints

- 1 <= s.length <= 20
- 1 <= p.length <= 20
- s contains only lowercase English letters.
- p contains only lowercase English letters, '.', and '*'.
- It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.

Brute Force Recursion

Intuition

A direct recursive approach that checks all possible matches by exploring every possibility of ’*’ and ’.’ characters.

Steps

• Base cases: if pattern is empty, string must also be empty for a match.
• If the next character in pattern is ’*’, consider two possibilities: zero occurrence or one/more occurrence.
• If current characters match or pattern has ’.’, proceed with the rest of string and pattern.

def isMatch(s: str, p: str) -> bool:
    if not p:
        return not s
    first_match = bool(s) and p[0] in {s[0], '.'}
    if len(p) >= 2 and p[1] == '*':
        return (isMatch(s, p[2:]) or
                (first_match and isMatch(s[1:], p)))
    else:
        return first_match and isMatch(s[1:], p[1:])

Complexity

• Time: O((T+P) * 2^(T+P/2)) where T is length of text and P is length of pattern
• Space: O((T+P) * 2^(T+P/2)) due to recursion stack in worst case
• Notes: Exponential time due to overlapping subproblems

Top-Down Memoization

Intuition

To optimize the brute-force approach by caching results of subproblems to avoid redundant computation.

Steps

• Use a memoization table (or dictionary) to store results of (i,j) pairs representing current positions in string and pattern.
• Before computing result for any (i,j), check if already computed.
• Otherwise, compute using same recurrence relation but store result in memo table.

def isMatch(s: str, p: str) -> bool:
    memo = {}
    def dp(i, j):
        if (i, j) in memo:
            return memo[(i, j)]
        if j == len(p):
            ans = i == len(s)
        else:
            first_match = i < len(s) and p[j] in {s[i], '.'}
            if j+1 < len(p) and p[j+1] == '*':
                ans = (dp(i, j+2) or
                       (first_match and dp(i+1, j)))
            else:
                ans = first_match and dp(i+1, j+1)
        memo[(i, j)] = ans
        return ans
    return dp(0, 0)

Complexity

• Time: O(T*P) where T is length of text and P is length of pattern
• Space: O(T*P) for memoization table
• Notes: Avoids recomputation of overlapping subproblems

Bottom-Up Dynamic Programming

Intuition

Build up solution from smaller subproblems using a 2D table, solving from end to beginning to ensure subproblems are solved before needed.

Steps

• Create a 2D boolean DP table where dp[i][j] represents whether s[i:] matches p[j:].
• Initialize base cases: dp[len(s)][len(p)] = true.
• Fill the table from bottom-right to top-left according to recurrence relation.

def isMatch(s: str, p: str) -> bool:
    dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
    dp[len(s)][len(p)] = True
    for i in range(len(s), -1, -1):
        for j in range(len(p) - 1, -1, -1):
            first_match = i < len(s) and p[j] in {s[i], '.'}
            if j+1 < len(p) 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]

Complexity

• Time: O(T*P) where T is length of text and P is length of pattern
• Space: O(T*P) for the DP table
• Notes: Bottom-up approach with iterative filling of DP table