Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:
'.' Matches any single character.​​​​'*' Matches zero or more of the preceding element.The matching should cover the entire input string (not partial).
Example 1:
Input: s = "aa", p = "a" Output: false Explanation: "a" does not match the entire string "aa".
Example 2:
Input: s = "aa", p = "a*" Output: true Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:
Input: s = "ab", p = ".*" Output: true Explanation: ".*" means "zero or more (*) of any character (.)".
Constraints:
1 <= s.length <= 201 <= p.length <= 20s contains only lowercase English letters.p contains only lowercase English letters, '.', and '*'.'*', there will be a previous valid character to match.Regular Expression Matching asks whether a string s matches a pattern p containing special characters . (matches any single character) and * (matches zero or more of the preceding element). A brute force recursive solution tries all possible interpretations of *, but this leads to heavy recomputation and exponential time.
A more efficient strategy uses Dynamic Programming. Define a DP state where dp[i][j] indicates whether the first i characters of s match the first j characters of p. The transitions depend on whether the current pattern character is a normal character, ., or *. When encountering *, you can either ignore the preceding element (zero occurrences) or consume characters from the string if they match.
This problem can be solved using either top-down recursion with memoization or bottom-up DP. Both approaches systematically avoid repeated work and correctly handle the pattern rules. The typical time complexity is O(m × n), where m and n are the lengths of the string and pattern.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Recursion with Memoization | O(m × n) | O(m × n) |
| Bottom-Up Dynamic Programming | O(m × n) | O(m × n) |
Tushar Roy - Coding Made Simple
This approach uses recursion with memoization to solve the problem efficiently. We recursively compare characters of the input string and the pattern, addressing special characters like '.' and '*'. The memoization is used to store results of sub-problems to avoid redundant calculations, which drastically improves the performance.
Time Complexity: O(m * n), where m and n are the lengths of the string and pattern, respectively. We solve every subproblem once and store the result.
Space Complexity: O(m * n) due to recursion stack and memoization storage.
1def isMatch(s, p):
2 memo = {}
3 def dfs(i, j):
4 if (i, j) inThe Python solution uses a depth-first search (DFS) approach with memoization to tackle overlapping subproblems. We check if characters at position i in the string and j in the pattern match directly or through special symbols. The '*' in the pattern is handled by either skipping it or considering it as multiple matches.
This approach involves using a DP table to solve the problem by filling up a boolean matrix iteratively. This avoids recursion and stacks overhead, improving performance in certain scenarios. Each cell in the table represents whether the substring of the pattern matches the substring of the input.
Time Complexity: O(m * n) since we traverse the complete matrix.
Space Complexity: O(m * n) due to the DP table used to store subproblem solutions.
1Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Regular Expression Matching is a well-known hard problem frequently discussed in FAANG-level interviews. It tests understanding of recursion, dynamic programming, and careful handling of pattern-matching rules.
The optimal approach uses dynamic programming. By defining a DP state that represents whether prefixes of the string and pattern match, you can systematically handle '.' and '*' rules while avoiding repeated computations.
Dynamic programming is used because many subproblems repeat when exploring different interpretations of '*'. Storing intermediate results ensures each state is computed only once, improving performance significantly.
A 2D DP table or memoization map is commonly used. It stores whether a substring of the input string matches a substring of the pattern, enabling efficient state transitions.
The Python DP solution constructs a 2D boolean array where dp[i][j] signifies if the first i characters of the string match the first j characters of the pattern. The matrix is initialized with the base conditions and filled based on the characters in pattern string, iteratively updating for mismatches dictated by '*' or '.'.