# Leetcode 10 Solution

https://leetcode.com/problems/regular-expression-matching

## Thinking Process

For this question, we are going to simulate the matching process of the regex. Let’s first assume `M(i, j)` means whether `s[i:]` can be matched by `p[j:]`. We can calculate `M(i, j)` recursively.

• If `i == len(s)` and `j == len(p)`, we have a match.
• If `i != len(s)` and `j == len(p)`, they don’t match.
• Otherwise, there are three rules to move forward:
• If `p[j + 1]` is `*`, that means we can use `p[j]` to match any number of it in `s`, and then we can focus on a smaller scale problem, which `M(i + k, j + 2)`, where `k` is the number of `p[j]` matched after `s[i]`.
• If `p[j]` is `.`, we go into `M(i + 1, j + 1)`.
• If `s[i] == p[j]`, we go into `M(i + 1, j + 1)`.
• Otherwise, there is no match.

The result of the original question is `M(0, 0)`.

## Time & Space Complexity

Assuming `M` is the size of `s`, `N` is the size of `p`

• Time complexity: `O(M^N)` (because in the recursion, we go `N` layers, and for each layer, there are at most `M` branches)
• Space complexity: `O(N)`

## Solution

``````class Solution:
def isMatch(self, s: str, p: str) -> bool:

@functools.cache
def is_match(s, p, i, j):
while j < len(p):
if j + 1 < len(p) and p[j + 1] == '*':
for k in range(i, len(s)):
if is_match(s, p, k, j + 2):
return True

if not (p[j] == '.' or p[j] == s[k]):
break
else:
if is_match(s, p, len(s), j + 2):
return True
return False

if i < len(s) and (p[j] == '.' or p[j] == s[i]):
i += 1
j += 1
else:
break

if j == len(p):
return i == len(s)

return False

return is_match(s, p, 0, 0)
``````