How to Solve Regular Expression Matching
Regular Expression Matching Introduction
Regular Expression Matching Introduction
The Regular Expression Matching problem asks us to validate whether a pattern p matches an input string. The problem requires us to create a dynamic programming table, moving through each cell, updating its value based on a set of rules correlating to the rules set up in the original question.
Regular Expression Matching Problem
Regular Expression Matching Problem
Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Example Inputs and Outputs
Example 1
Input: s = "aa", p = "a"
Output: false
Example 2
Input: s = "aa", p = "a*"
Output: True
Example 3
Input: s = "ab", p = ".*"
Output: true
Regular Expression Matching Solutions
Regular Expression Matching Solutions
To solve this problem, we use dynamic programming to determine whether a given string matches a pattern. We create a dynamic programming table of size (m + 1) x (n + 1), where m is the length of the string and n is the length of the pattern. Each cell in the table represents whether a substring of the string and a substring of the pattern match.
We start by initializing the table with False values. Then, we set the first cell to True because an empty string matches an empty pattern. Moving through each cell in the table, we update its value based on specific rules.
If the pattern character is a letter or '.', we compare the current string character to the current pattern character. If they match, the current cell's value depends on the previous matching state. Otherwise, the current cell remains False.
If the pattern character is ''", we have two possibilities. The ''" can match zero occurrences of the preceding element, in which case we consider the pattern without the preceding element. Alternatively, the '*' can match one or more occurrences of the preceding element. We check if the current string character matches the preceding pattern character, and if they do, the current cell's value depends on a previous cell.
Finally, we obtain the result from the last cell in the table, indicating whether the entire string matches the entire pattern.
def isMatch(s, p):
m, n = len(s), len(p)
# Create a 2D boolean array to store the matching results
dp = [[False] * (n + 1) for _ in range(m + 1)]
# Base case: an empty pattern matches an empty string
dp[0][0] = True
# Update the first row to handle patterns with '*'
for j in range(2, n + 1):
if p[j - 1] == '*':
dp[0][j] = dp[0][j - 2]
# Fill in the rest of the dp array
for i in range(1, m + 1):
for j in range(1, n + 1):
if p[j - 1] == s[i - 1] or p[j - 1] == '.':
# Characters match or pattern has '.'
dp[i][j] = dp[i - 1][j - 1]
elif p[j - 1] == '*':
# Pattern has '*', check the preceding character
dp[i][j] = dp[i][j - 2]
if p[j - 2] == s[i - 1] or p[j - 2] == '.':
dp[i][j] |= dp[i - 1][j]
return dp[m][n]
# Driver code
s = "cbaab"
p = "c.a*b"
result = isMatch(s, p)
print(f"String '{s}' matches pattern '{p}': {result}")
#expected result is True1def isMatch(s, p):
2 m, n = len(s), len(p)
3
4 # Create a 2D boolean array to store the matching results
5 dp = [[False] * (n + 1) for _ in range(m + 1)]
6
7 # Base case: an empty pattern matches an empty string
8 dp[0][0] = True
9
10 # Update the first row to handle patterns with '*'
11 for j in range(2, n + 1):
12 if p[j - 1] == '*':
13 dp[0][j] = dp[0][j - 2]
14
15 # Fill in the rest of the dp array
16 for i in range(1, m + 1):
17 for j in range(1, n + 1):
18 if p[j - 1] == s[i - 1] or p[j - 1] == '.':
19 # Characters match or pattern has '.'
20 dp[i][j] = dp[i - 1][j - 1]
21 elif p[j - 1] == '*':
22 # Pattern has '*', check the preceding character
23 dp[i][j] = dp[i][j - 2]
24 if p[j - 2] == s[i - 1] or p[j - 2] == '.':
25 dp[i][j] |= dp[i - 1][j]
26
27 return dp[m][n]
28
29# Driver code
30s = "cbaab"
31p = "c.a*b"
32result = isMatch(s, p)
33print(f"String '{s}' matches pattern '{p}': {result}")
34
35#expected result is TrueTime/Space Complexity Analysis
- Time Complexity: O(m * n), where m is the length of the string s and n is the length of the pattern p. This is because we need to iterate through each character in the string and pattern to fill the dynamic programming table.
- Space Complexity: O(m * n), as we need to create a dynamic programming table to store the intermediate results.
About interviewing.io
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
