Regular Expression Matching
You are given an input string s consisting of lowercase english letters, and a pattern p consisting of lowercase english letters, as well as '.', and '*' characters.
Return true if the pattern matches the entire input string, otherwise return false.
'.'Matches any single character'*'Matches zero or more of the preceding element.
Example 1:
Input: s = "aa", p = ".b"
Output: falseExplanation: Regardless of which character we choose for the '.' in the pattern, we cannot match the second character in the input string.
Example 2:
Input: s = "nnn", p = "n*"
Output: trueExplanation: '*' means zero or more of the preceding element, 'n'. We choose 'n' to repeat three times.
Example 3:
Input: s = "xyz", p = ".*z"
Output: trueExplanation: The pattern ".*" means zero or more of any character, so we choose ".." to match "xy" and "z" to match "z".
Constraints:
1 <= s.length <= 201 <= p.length <= 20- Each appearance of
'*', will be preceded by a valid character or'.'.
Recommended Time & Space Complexity
You should aim for a solution as good or better than O(m * n) time and O(m * n) space, where m is the length of the string s and n is the length of the string p.
Hint 1
Try to think in terms of recursion and visualize it as a decision tree, where we explore different combinations to match the strings when encountering *. Multiple decisions are made at each step to find a valid matching path. Can you determine the possible decisions at each recursion step?
Hint 2
We recursively iterate through the strings using indices i and j for s and p, respectively. If the characters match or p[j] is '.', we increment both i and j to process the remaining strings. When the next character of string p is '*', we have two choices: skip it (treating it as zero occurrences) or match one or more characters (if s[i] matches p[j]), incrementing i accordingly.
Hint 3
If both indices go out of bounds, we return true; otherwise, we return false. If any recursive path returns true, we immediately return true. This approach is exponential. Can you think of a way to optimize it?
Hint 4
We can use memoization to cache the results of recursive calls and avoid redundant calculations. A hash map or a 2D array can be used to store these results.