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.Problem Overview: Given a string s and a pattern p, determine if the entire string matches the pattern. The pattern supports two special characters: . which matches any single character, and * which matches zero or more of the preceding element. The match must cover the whole string, not just a substring.
Approach 1: Recursive Backtracking with Memoization (Time: O(m*n), Space: O(m*n))
The natural way to reason about the problem is recursion. Compare characters from left to right and decide how the pattern behaves. When the next character in the pattern is *, you have two choices: treat it as matching zero characters (skip the pattern segment) or consume one matching character from the string and stay on the same pattern index. Without caching, this branching causes exponential work. Memoization stores results for each state (i, j) representing whether s[i:] matches p[j:]. Each state is computed once, reducing complexity to O(m*n). This approach closely mirrors the recursive definition of regex rules and is easier to reason about when first learning the problem. It combines recursion with dynamic programming to avoid repeated work.
Approach 2: Dynamic Programming Tabulation (Time: O(m*n), Space: O(m*n))
Bottom‑up dynamic programming converts the recursive states into a table. Define dp[i][j] as whether the first i characters of the string match the first j characters of the pattern. Iterate through the table while handling three cases: direct character match, wildcard ., and star *. The star is the tricky part. It can represent zero occurrences (look two positions back in the pattern) or multiple occurrences if the preceding character matches the current string character. By filling the table row by row, every state depends only on previously computed states. This iterative version avoids recursion overhead and is usually preferred in production code. The solution relies heavily on reasoning about pattern transitions in string processing.
Recommended for interviews: Start by explaining the recursive idea since it mirrors how regex rules are defined. Then introduce memoization to remove exponential recomputation. Interviewers typically expect the O(m*n) dynamic programming solution because it demonstrates understanding of state design and pattern transitions. Showing both the recursive memoized solution and the bottom‑up DP version signals strong mastery of dynamic programming problems.
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.
The 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.
Java
C
C++
C#
JavaScript
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.
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.
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 '.'.
Java
C
C++
C#
JavaScript
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.
| Approach | Complexity |
|---|---|
| Recursive Approach with Memoization | 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. |
| Dynamic Programming Tabulation | Time Complexity: O(m * n) since we traverse the complete matrix. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Backtracking with Memoization | O(m*n) | O(m*n) | When explaining the problem conceptually or deriving the solution from recursive pattern rules |
| Dynamic Programming Tabulation | O(m*n) | O(m*n) | Preferred iterative solution in interviews and production due to predictable state transitions |
Regular Expression Dynamic Programming • Tushar Roy - Coding Made Simple • 263,593 views views
Watch 9 more video solutions →Practice Regular Expression Matching with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor