Solution: Regular Expression Matching
Explore how to solve the regular expression matching problem by applying dynamic programming techniques. Understand how to use recursion with memoization to efficiently match patterns containing '.' and '*', covering the entire input string. This lesson guides you through managing overlapping subproblems and optimizing the process for a time complexity of O(S×P). Gain practical knowledge of recursion, memoization, and pointer manipulation for string and pattern matching.
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 ...