Solution: Regular Expression Matching
Explore how to solve the regular expression matching problem by applying dynamic programming techniques. Understand the use of recursion with memoization to handle patterns with '.' and '*' and optimize the solution from exponential to polynomial time complexity.
We'll cover the following...
Statement
You are given an input string, s, and a pattern string, p. Your task is to implement regular expression matching between s and p, where the pattern may include the special characters '.' and '*':
'.'matches any single character.'*'matches zero or more occurrences of the preceding character.
The match must cover the entire input string, not just part of it.
Constraints:
s.lengthp.lengthscontains only lowercase English letters.pcontains only lowercase English letters,'.', and'*'.It is guaranteed that for each appearance of the character
'*', there will be a previous valid character to match.
Solution
One of the first ideas that comes to mind to solve ...