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.

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)