Solution: Regular Expression Matching
Understand how to apply dynamic programming with memoization to solve regular expression matching problems. This lesson guides you through handling special characters '.', and '*', optimizing recursive solutions to avoid repeated calculations and achieve efficient matching across entire strings.
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 ...