## 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 = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, "c*a*b" 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(m*n), where m and n are the lengths of s and p respectively.
Space Complexity: O(m*n), the size of the dp array.

## Regular Expression Matching Solution Code

`1`