Solution: Regular Expression Matching
Explore how to implement regular expression matching between a string and a pattern including special characters '.' and '*'. Understand the use of recursion with memoization to avoid redundant calculations and achieve an efficient dynamic programming solution with time complexity O(m*n). This lesson helps you master the approach to match entire strings with patterns in coding interviews.
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 ...