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 means zero or more occurrences of the preceding element.
Approach 1: Recursive Approach with Memoization (Time: O(m*n), Space: O(m*n))
This method models the problem exactly how the pattern matching works conceptually. Start from indices i in the string and j in the pattern and recursively check if the remaining substrings match. When encountering *, two choices exist: skip the pattern segment (x*) or consume one matching character and stay on the same pattern index. Memoization stores results for states (i, j) to avoid recomputing overlapping subproblems. Without caching the recursion would explode exponentially, but memoization reduces it to O(m*n) since each state is computed once.
This approach is intuitive because it directly mirrors the matching rules of regular expressions. It is a strong choice when you want clear logic and quick implementation during interviews. The recursion depth is at most O(m + n), and the memo table ensures previously solved states are reused.
Approach 2: Dynamic Programming Tabulation (Time: O(m*n), Space: O(m*n))
The tabulation approach builds a bottom‑up DP table where dp[i][j] represents whether the first i characters of the string match the first j characters of the pattern. The transition depends on the current pattern character. If characters match directly or through ., inherit the result from dp[i-1][j-1]. If the pattern contains *, handle two cases: treat x* as zero occurrences (dp[i][j-2]) or consume one matching character if s[i-1] matches the preceding pattern character (dp[i-1][j]).
The DP table is filled row by row, carefully initializing cases where patterns like a*, a*b*, or similar can match an empty string. This approach removes recursion entirely and guarantees predictable performance with O(m*n) time and space complexity. It is often easier to debug because every subproblem is visible in the table.
Both approaches rely on breaking the problem into smaller matching states. They heavily use concepts from String processing and Dynamic Programming, while the first approach also demonstrates recursive state exploration from Recursion.
Recommended for interviews: Interviewers typically expect the dynamic programming formulation because it clearly demonstrates understanding of state transitions and overlapping subproblems. Starting with the recursive reasoning and then adding memoization shows strong problem‑solving skills, while presenting the tabulation DP proves you can convert recursive thinking into an efficient iterative solution.
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.
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 '.'.
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.
We design a function dfs(i, j), which indicates whether the i-th character of s matches the j-th character of p. The answer is dfs(0, 0).
The calculation process of the function dfs(i, j) is as follows:
j has reached the end of p, then if i has also reached the end of s, the match is successful, otherwise, the match fails.j is '*', we can choose to match 0 s[i] characters, which is dfs(i, j + 2). If i \lt m and s[i] matches p[j], we can choose to match 1 s[i] character, which is dfs(i + 1, j).j is not '*', then if i \lt m and s[i] matches p[j], it is dfs(i + 1, j + 1). Otherwise, the match fails.During the process, we can use memoization search to avoid repeated calculations.
The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the lengths of s and p respectively.
We can convert the memoization search in Solution 1 into dynamic programming.
Define f[i][j] to represent whether the first i characters of string s match the first j characters of string p. The answer is f[m][n]. Initialize f[0][0] = true, indicating that the empty string and the empty regular expression match.
Similar to Solution 1, we can discuss different cases.
p[j - 1] is '*', we can choose to match 0 s[i - 1] characters, which is f[i][j] = f[i][j - 2]. If s[i - 1] matches p[j - 2], we can choose to match 1 s[i - 1] character, which is f[i][j] = f[i][j] \lor f[i - 1][j].p[j - 1] is not '*', then if s[i - 1] matches p[j - 1], it is f[i][j] = f[i - 1][j - 1]. Otherwise, the match fails.The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the lengths of s and p respectively.
| 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. |
| Memoization Search | — |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive with Memoization | O(m*n) | O(m*n) | When explaining the problem recursively or deriving the DP state from first principles |
| Dynamic Programming Tabulation | O(m*n) | O(m*n) | Preferred in interviews for deterministic performance and clear state transitions |
Regular Expression Matching - Dynamic Programming Top-Down Memoization - Leetcode 10 • NeetCode • 233,630 views views
Watch 9 more video solutions →Practice Regular Expression Matching with our built-in code editor and test cases.
Practice on FleetCode