How do you solve Regular Expression Matching on LeetCode?

Regular Expression Matching (LeetCode #10) can be solved using Brute Force or Optimal Solution (Dynamic Programming). The optimal approach is Optimal Solution (Dynamic Programming) with O(n*m) time complexity and O(n*m) space complexity. Key insight: Recognizing that '*' can represent zero or more occurrences of the preceding character is crucial for breaking down the problem.

What is the time complexity of Regular Expression Matching?

The optimal solution for Regular Expression Matching runs in O(n*m) time and uses O(n*m) space. The time complexity is O(n*m) because we are filling a table of size n (length of s) by m (length of p). Each cell takes constant time to compute.

What is the brute force solution for Regular Expression Matching?

The brute force approach for Regular Expression Matching is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach tries to match the string with the pattern recursively. For each character in the string, we check if it matches the current character in the pattern or if the pattern character is a wildcard ('.') or followed by a '*'. The optimal Optimal Solution (Dynamic Programming) approach improves this to O(n*m).

What algorithm or data structure is used to solve Regular Expression Matching?

Regular Expression Matching uses the following concepts: String, Dynamic Programming, Recursion. The recommended patterns to study are: Hash Map, Array, Two Pointers.

What are the interview tips for Regular Expression Matching?

When you first see this problem, clarify the rules for '.' and '*' to ensure you understand their behavior. Communicate your thought process clearly, showing how you would break down the problem into smaller parts. Mention edge cases like empty strings and patterns, as they can often lead to off-by-one errors.

What are common mistakes when solving Regular Expression Matching?

Students often forget to handle the case where '*' can match zero occurrences. Not initializing the DP table correctly can lead to incorrect results.

#10

Regular Expression Matching

Hard

StringDynamic ProgrammingRecursionHash MapArrayTwo Pointers

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution (Dynamic Programming)★
Time	O(n²)	O(n*m)
Space	O(1)	O(n*m)

💡

Intuition

Time O(n*m)Space O(n*m)

The optimal approach uses dynamic programming to store results of subproblems in a table, avoiding redundant calculations. This way, we can build up the solution based on previously computed results.

⚙️

Algorithm

5 steps

1Step 1: Create a 2D DP table where dp[i][j] indicates whether s[0...i-1] matches p[0...j-1].
2Step 2: Initialize dp[0][0] to True (empty string matches empty pattern).
3Step 3: Handle patterns with '*' that can match empty strings.
4Step 4: Fill the DP table based on the matching rules for '.' and '*'.
5Step 5: Return the value in dp[len(s)][len(p)] as the final result.

solution.py20 lines

1# Full working Python code with comments
2
3def isMatch(s: str, p: str) -> bool:
4    dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
5    dp[0][0] = True
6
7    # Handle patterns like a*, a*b*, etc.
8    for j in range(1, len(p) + 1):
9        if p[j - 1] == '*':
10            dp[0][j] = dp[0][j - 2]
11
12    for i in range(1, len(s) + 1):
13        for j in range(1, len(p) + 1):
14            first_match = (s[i - 1] == p[j - 1] or p[j - 1] == '.')
15            if p[j - 1] == '*':
16                dp[i][j] = dp[i][j - 2] or (first_match and dp[i - 1][j])
17            else:
18                dp[i][j] = first_match and dp[i - 1][j - 1]
19
20    return dp[len(s)][len(p)]

ℹ

Complexity note: The time complexity is O(n*m) because we are filling a table of size n (length of s) by m (length of p). Each cell takes constant time to compute.

1Recognizing that '*' can represent zero or more occurrences of the preceding character is crucial for breaking down the problem.
2Understanding how to set up a DP table can help in many string matching problems, not just regex.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.