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 = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".


Example 3:


Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".


Example 4:


Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".


Example 5:


Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Complete search

String algorithms

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

Solutions:
class Solution:
	cache = {}

	def isMatch(self, s, p):
		if (s, p) in self.cache:
			return self.cache[s, p]
		if not p:
			return not s
		if p[-1] == '*':
			if self.isMatch(s, p[:-2]):
				self.cache[s, p] = True
				return True
			if s and (s[-1] == p[-2] or p[-2] == '.') and self.isMatch(s[:-1], p):
				self.cache[s, p] = True
				return True
		if s and (p[-1] == s[-1] or p[-1] == '.') and self.isMatch(s[:-1], p[:-1]):
			self.cache[s, p] = True
			return True
		self.cache[s, p] = False
		return False


class Solution(object):

	def isMatch(self, string, expr):
		self.memo = {(0, 0): True}
		self.string = string
		self.expr = expr
		N = len(string)
		M = len(expr)
		return self.get(N, M)

	def get(self, i, j):
		if i < 0 or j < 0:
			return False
		if (i, j) not in self.memo:
			self.memo[i, j] = self.eval(i, j)
		return self.memo[i, j]

	def eval(self, i, j):
		if j <= 0:
			return False
		if self.expr[j - 1] == '*':
			prev_char = self.expr[j - 2]
			if prev_char == '.' or (i >= 1 and prev_char == self.string[i - 1]):
				if self.get(i - 1, j):
					return True
			return self.get(i, j - 2)
		else:
			if self.expr[j - 1] == '.' or (i >= 1 and self.expr[j - 1] == self.string[i - 1]):
				return self.get(i - 1, j - 1)
			return False


class Solution:

	def isMatch(self, s, p):
		self.mem = {}
		self.t = s
		self.p = p
		return self.match(0, 0)

	def match(self, i, j):
		if (i, j) not in self.mem:
			if j == len(self.p):
				res = i == len(self.t)
			elif j + 1 < len(self.p) and self.p[j + 1] == '*':
				res = self.match(i, j + 2) or (i < len(self.t) and self.p[j] in {self.t[i], '.'} and self.match(i + 1, j))
			else:
				res = i < len(self.t) and self.p[j] in {self.t[i], '.'} and self.match(i + 1, j + 1)
			self.mem[i, j] = res
		return self.mem[i, j]


class Solution:

	def __init__(self):
		self.dp = {}

	def isMatch(self, text, pattern):
		if not pattern:
			return not text
		if (text, pattern) in self.dp:
			return self.dp[text, pattern]
		first_match = bool(text) and pattern[0] in {text[0], '.'}
		if len(pattern) >= 2 and pattern[1] == '*':
			self.dp[text, pattern] = self.isMatch(text, pattern[2:]) or (first_match and self.isMatch(text[1:], pattern))
		else:
			self.dp[text, pattern] = first_match and self.isMatch(text[1:], pattern[1:])
		return self.dp[text, pattern]


class Solution:

	def isMatch(self, s, p):

		def parsePatern(p):
			pi = len(p) - 1
			while pi >= 0:
				if p[pi] == '*':
					if pi == 0:
						raise Exception('Invalid pattern!')
					yield (p[pi - 1], 1)
					pi -= 2
				else:
					yield (p[pi], 0)
					pi -= 1
		from collections import deque
		if not p:
			return p == s
		plist = list(parsePatern(p))
		P = len(plist)
		q = set([(0, len(s) - 1)])
		seen = set()
		while q:
			(pat_i, si) = q.pop()
			if (pat_i, si) in seen:
				continue
			seen.add((pat_i, si))
			(pat, is_as) = plist[pat_i] if pat_i < P else ('', 0)
			if not pat and si < 0:
				return True
			if is_as:
				q.add((pat_i + 1, si))
				while si >= 0 and (s[si] == pat or pat == '.'):
					si -= 1
					q.add((pat_i + 1, si))
			elif si >= 0 and (s[si] == pat or pat == '.'):
				q.add((pat_i + 1, si - 1))
		return False


class Solution:

	def isMatch(self, s, p):
		if not p and len(s) != 0:
			return False
		memo = {}

		def dp(i, j):
			if (i, j) not in memo:
				if j == len(p):
					res = i == len(s)
				else:
					head_match = i < len(s) and p[j] in {s[i], '.'}
					if j + 1 < len(p) and p[j + 1] == '*':
						res = dp(i, j + 2) or (head_match and dp(i + 1, j))
					else:
						res = head_match and dp(i + 1, j + 1)
				memo[i, j] = res
			return memo[i, j]
		return dp(0, 0)


class Solution:

	def isMatch(self, s, p):
		self.maps = dict()
		return self.dfs(s, p)

	def dfs(self, s, p):
		key = (s, p)
		if key in self.maps:
			return self.maps[key]
		if not s and (not p):
			return True
		if s and (not p):
			return False
		if len(p) > 1 and p[1] == '*':
			if s and s[0] == p[0] or (p[0] == '.' and s):
				self.maps[key] = self.dfs(s[1:], p[2:]) or self.dfs(s[1:], p) or self.dfs(s, p[2:])
			else:
				self.maps[key] = self.dfs(s, p[2:])
		elif s and s[0] == p[0] or (p[0] == '.' and s):
			self.maps[key] = self.dfs(s[1:], p[1:])
		return self.maps[key] if key in self.maps else False


class Solution:

	def isMatch(self, s, p):
		(m, n) = (len(s), len(p))
		dp = [[False] * (n + 1) for _ in range(m + 1)]
		dp[0][0] = True
		for j in range(2, n + 1):
			if p[j - 1] == '*':
				dp[0][j] = dp[0][j - 2]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if p[j - 1] == '*':
					if p[j - 2] == s[i - 1] or p[j - 2] == '.':
						dp[i][j] = dp[i - 1][j] or dp[i][j - 1] or dp[i][j - 2]
					elif p[j - 2] != s[i - 1]:
						dp[i][j] = dp[i][j - 2]
				elif p[j - 1] == s[i - 1] or p[j - 1] == '.':
					dp[i][j] = dp[i - 1][j - 1]
		return dp[m][n]


class Solution:

	def isMatch(self, s, p):
		m = {}

		def dp(i, j):
			print((i, j))
			if (i, j) not in m:
				if j == len(p):
					ans = i == len(s)
				else:
					first_match = i < len(s) and p[j] in {s[i], '.'}
					if j + 1 < len(p) and p[j + 1] == '*':
						ans = dp(i, j + 2) or (first_match and dp(i + 1, j))
					else:
						ans = first_match and dp(i + 1, j + 1)
				m[i, j] = ans
			return m[i, j]
		return dp(0, 0)


class Solution:

	def isMatch(self, s, p):
		dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
		dp[-1][-1] = True
		for i in range(len(s), -1, -1):
			for j in range(len(p) - 1, -1, -1):
				first_match = i < len(s) and p[j] in {s[i], '.'}
				if j + 1 < len(p) and p[j + 1] is '*':
					dp[i][j] = dp[i][j + 2] or (first_match and dp[i + 1][j])
				else:
					dp[i][j] = first_match and dp[i + 1][j + 1]
		return dp[0][0]


class Solution:

	def isMatch(self, s, p):
		import re
		pattern = re.compile(p)
		match = pattern.match(s)
		if match:
			try:
				return match.group() == s
			except:
				return False
			finally:
				pass
		else:
			return False