Similar Problems
Similar Problems not available
Regular Expression Matching - Leetcode Solution
LeetCode: Regular Expression Matching Leetcode Solution
Difficulty: Hard
Topics: string dynamic-programming
Problem Statement
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).
Note:
s could be empty and contains only lowercase letters a-z. p could be empty and contains only lowercase letters a-z, and characters like . or *.
Example 1: Input: s = "aa", p = "a" Output: false Explanation: "a" does not match the entire string "aa".
Example 2: Input: s = "aab", p = "cab" Output: true Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, "cab" matches "aab".
Solution
To solve this problem, we can use a dynamic programming approach. We can create a two-dimensional boolean array dp, where dp[i][j] represents whether the substring of s from 0 to i-1 can be matched with the substring of p from 0 to j-1.
Here are the steps to fill out the dp array:
- Initialize dp[0][0] as true since an empty string can match another empty string.
- Fill in the first row dp[0][j] according to the pattern. If p[j-1] is '', then dp[0][j] is equal to dp[0][j-2] (because '''' means zero or more of the preceding element).
- Fill in the first column dp[i][0] as false since a non-empty string cannot match an empty pattern.
- For each dp[i][j], if s[i-1] == p[j-1] or p[j-1] == '.', we can match the characters. Therefore, dp[i][j] is equal to dp[i-1][j-1].
- If p[j-1] == '', there are two cases to consider: a) if p[j-2] == s[i-1] or p[j-2] == '.', the '' can either match zero or more characters. Therefore, we need to check dp[i][j-2] (zero match) or dp[i-1][j] (one or more matches) b) if p[j-2] != s[i-1], the '*' can only match zero characters. Therefore, dp[i][j] is equal to dp[i][j-2]
Finally, we return dp[m][n], where m and n are the lengths of s and p respectively.
Here is the Python code for the solution:
class Solution: def isMatch(self, s: str, p: str) -> bool: m, n = len(s), len(p) dp = [[False] * (n + 1) for _ in range(m + 1)] dp[0][0] = True
# Fill in the first row dp[0][j]
for j in range(2, n + 1):
if p[j-1] == '*':
dp[0][j] = dp[0][j-2]
# Fill in the first column dp[i][0]
# (Already initialized as False)
# Fill in the rest of the dp array
for i in range(1, m + 1):
for j in range(1, n + 1):
if s[i-1] == p[j-1] or p[j-1] == '.':
dp[i][j] = dp[i-1][j-1]
elif p[j-1] == '*':
if p[j-2] == s[i-1] or p[j-2] == '.':
dp[i][j] = dp[i][j-2] or dp[i-1][j]
else:
dp[i][j] = dp[i][j-2]
return dp[m][n]
Time Complexity: O(mn), where m and n are the lengths of s and p respectively. Space Complexity: O(mn), the size of the dp array.
Regular Expression Matching Solution Code
1