# LC010 - Regular Expression Matching

## Problem

Given an input string `s` and a pattern `p`, implement regular expression matching with support for `'.'` and `'*'` where:

* `'.'` Matches any single character.​​​​
* `'*'` Matches zero or more of the preceding element.

The matching should cover the **entire** input string (not partial).

### Example

**Input:** s = "aa", p = "a"

**Output:** false

**Explanation:** "a" does not match the entire string "aa".

## Solution

#### DFS

The naive approach to traverse the entire parsing decision tree is $$O(2^n)$$ in time complexity.

#### DFS Cache

With a cache, we can get it down to $$O(m\cdot n)$$, at the cost of extra space.

```python
def isMatch(self, s: str, p: str) -> bool:
	@cache
	def dfs(i, j):
		if i >= len(s) and j >= len(p):
			return True
		if j >= len(p):
			return False

		match = i < len(s) and (s[i] == p[j] or p[j] == ".")
		if (j+1) < len(p) and p[j+1] == "*":
			return (dfs(i, j+2) or (match and dfs(i+1, j)))
		if match:
			return dfs(i+1, j+1)
		return False
	return dfs(0,0)
```