#10

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Regular Expression Matching

The Regular Expression Matching problem involves checking if a string matches a pattern using '.' and '*'.

Problem Statement

You are given a string s and a pattern p. Your goal is to implement a function that returns true if the string matches the pattern and false otherwise. The pattern can include the following special characters: '.' which matches any single character, and '*' which matches zero or more of the preceding element.

The matching should cover the entire string s, not just part of it. For example, a string of 'aa' and pattern 'a*' should return true, as '*' allows for matching zero or more 'a's.

Examples

Example 1

Input: s = "aa", p = "a"

Output: false

"a" does not match the entire string "aa".

Example 2

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

Output: true

'*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3

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

Output: true

"." 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.

Solution Approach

State Transition Dynamic Programming

This problem can be solved using dynamic programming where each state represents a substring of the string and pattern. By transitioning through states based on the characters of both the string and the pattern, you can decide if a match is possible.

Recursive Helper Function

A recursive solution can be implemented to check for matches between substrings, taking into account the special cases for '.' and '*'. This approach builds on smaller subproblems by considering each character in the string and pattern.

Memoization to Optimize Recursion

Memoization helps in avoiding repeated calculations. By storing previously computed results of subproblems, we can reduce the time complexity, especially when the string or pattern contains many repeating characters.

Complexity Analysis

Metric	Value
Time	Let
Space	The only memory we use is the

The time complexity of the solution is O(m * n), where m is the length of the string s and n is the length of the pattern p. The space complexity is O(m * n) due to the memoization table storing the results of subproblems.

What Interviewers Usually Probe

Assess understanding of dynamic programming, especially with state transitions.
Check if the candidate can handle special cases like empty strings or patterns with consecutive '*' and '.' characters.
Evaluate the candidate’s ability to optimize recursive solutions using memoization.

Common Pitfalls or Variants

Common pitfalls

Failing to handle edge cases like empty string s or pattern p properly.
Not correctly implementing the handling of '*' to match zero occurrences of the preceding character.
Overcomplicating the solution without leveraging dynamic programming or recursion effectively.

Follow-up variants

Extend the problem to match the pattern with case sensitivity or allow more complex special characters.
Solve the problem with a greedy approach instead of dynamic programming.
Modify the problem to check for partial string matching rather than complete string matching.

FAQ

How do I solve the Regular Expression Matching problem?

Use dynamic programming to build a table that checks all possible matches between substrings of the string and pattern, considering the special characters '.' and '*'.

What is the time complexity of solving Regular Expression Matching?

The time complexity is O(m * n), where m is the length of the string and n is the length of the pattern.

What is the role of '*' in the Regular Expression Matching?

'*' matches zero or more occurrences of the preceding character in the pattern, allowing flexibility in matching repetitive characters.

How does state transition dynamic programming apply here?

State transition dynamic programming helps solve the problem by systematically transitioning through the states of substrings of s and p to verify a match.

Can I solve Regular Expression Matching without dynamic programming?

While possible, solving the problem without dynamic programming would result in inefficient recursive solutions, leading to high time complexity due to repeated subproblem evaluations.

terminal

Solution

Solution 1: Memoization Search

We design a function $dfs(i, j)$, which indicates whether the $i$-th character of $s$ matches the $j$-th character of $p$. The answer is $dfs(0, 0)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        @cache
        def dfs(i, j):
            if j >= n:
                return i == m
            if j + 1 < n and p[j + 1] == '*':
                return dfs(i, j + 2) or (
                    i < m and (s[i] == p[j] or p[j] == '.') and dfs(i + 1, j)
                )
            return i < m and (s[i] == p[j] or p[j] == '.') and dfs(i + 1, j + 1)

        m, n = len(s), len(p)
        return dfs(0, 0)

Solution 2: Dynamic Programming

We can convert the memoization search in Solution 1 into dynamic programming.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        @cache
        def dfs(i, j):
            if j >= n:
                return i == m
            if j + 1 < n and p[j + 1] == '*':
                return dfs(i, j + 2) or (
                    i < m and (s[i] == p[j] or p[j] == '.') and dfs(i + 1, j)
                )
            return i < m and (s[i] == p[j] or p[j] == '.') and dfs(i + 1, j + 1)

        m, n = len(s), len(p)
        return dfs(0, 0)

Continue Practicing

#44 wildcard matching #241 different ways to add parentheses #5 longest palindromic substring