# Leetcode Regular Expression Matching problem solution in Python

Feb 13, 2023

In the Leetcode Regular Expression Matching problem solution in Python programming 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).

## Leetcode Regular Expression Matching problem solution in Python programming

``````class Solution:
# @return a boolean
def __init__(self):
self.cache = {}

def isMatch(self, s, p):
#If the next character of p is NOT ‘*’, then it must match the current character of s. Continue pattern matching with the next character of both s and p.
#If the next character of p is ‘*’, then we do a brute force exhaustive matching of 0, 1, or more repeats of current character of p… Until we could not match any more characters.
if (s, p) in self.cache: return self.cache[(s,p)]
if p == "":
self.cache[(s,p)] = s == ""
return s == ""
#next char is not "*", must match current char
if len(p) == 1 or p[1] != "*":
self.cache[(s,p)] = s != "" and (p[0] == s[0] or p[0] == ".") and self.isMatch(s[1:], p[1:])
return self.cache[(s,p)]
#next char is "*", take current char into consideration
i = 0
while i < len(s) and (p[0] == s[i] or p[0] == "."):
if self.isMatch(s[i:], p[2:]):
self.cache[(s,p)] = True
return True
i += 1

self.cache[(s,p)] = self.isMatch(s[i:], p[2:])
return self.cache[(s,p)]``````

#### By Neha Singhal

Hi, my name is Neha singhal a software engineer and coder by profession. I like to solve coding problems that give me the power to write posts for this site.