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)]Also read,
- Leetcode Regular Expression Matching problem solution in C++
- Leetcode Regular Expression Matching problem solution in Java
- Leetcode Regular Expression Matching problem solution in C
- Leetcode Regular Expression Matching problem solution in C#