Skip to main content
Talentd

Regular Expression Matching - Solution & Explanation

HardStringDynamic ProgrammingRecursion43 min readAsked at: Amazon, Microsoft, Apple +22
Practice this problem

Problem Statement

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 <= 20
  • 1 <= p.length <= 20
  • s contains only lowercase English letters.
  • p contains only lowercase English letters, '.', and '*'.
  • It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.

Approach Overview

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.

Approach 1: Recursive Approach with Memoization

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.

Code

PythonJavaCC++C#JavaScript

Python

Java

C

C++

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Dynamic Programming Tabulation

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 '.'.

Code

PythonJavaCC++C#JavaScript

Python

Java

C

C++

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Memoization Search

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:

  • If 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.
  • If the next character of 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).
  • If the next character of 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.

Code

PythonJavaC++GoRustJavaScriptC#CPHP

Python

Java

C++

Go

Rust

JavaScript

C#

C

PHP

Try this approach in the editor →

Approach 4: Dynamic Programming

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.

  • If 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].
  • If 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.

Code

PythonJavaC++GoRustJavaScriptC#PHPC

Python

Java

C++

Go

Rust

JavaScript

C#

PHP

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(m * n) due to recursion stack and memoization storage.

Dynamic Programming Tabulation

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.

Memoization Search—
Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive with MemoizationO(m*n)O(m*n)When explaining the problem recursively or deriving the DP state from first principles
Dynamic Programming TabulationO(m*n)O(m*n)Preferred in interviews for deterministic performance and clear state transitions

Video Solution

Regular Expression Dynamic Programming • Tushar Roy - Coding Made Simple • 274,114 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Regular Expression Matching easy or hard?
Regular Expression Matching is classified as a Hard problem because handling the '*' operator introduces branching decisions and overlapping subproblems. A correct solution requires careful dynamic programming state design and precise handling of pattern edge cases.
Regular Expression Matching Python/Java solution
Python and Java implementations typically use either memoized recursion with a dictionary or a 2D DP array. Both follow the same transitions: direct character match or '.', and special handling for '*' that allows skipping the preceding element or consuming characters repeatedly.
How to solve Regular Expression Matching in O(n)?
Regular Expression Matching cannot generally be solved in O(n) time because the pattern may contain '*' operators that create multiple matching possibilities. The standard optimal approach evaluates all combinations of string and pattern prefixes, resulting in O(m*n) complexity using dynamic programming.
What is the best approach for Regular Expression Matching?
Dynamic programming is the most reliable approach. Both memoized recursion and bottom-up tabulation evaluate states (i, j) representing prefixes of the string and pattern, leading to O(m*n) time complexity. The tabulation version is often preferred in interviews because it clearly shows state transitions and avoids recursion overhead.
Is Regular Expression Matching asked at Google/Amazon/Meta?
Regular Expression Matching is a well-known hard interview problem frequently discussed in preparation resources for companies like Google, Amazon, and Meta. It tests dynamic programming design, recursion with memoization, and careful handling of edge cases involving pattern operators.
What data structure is used in Regular Expression Matching?
The main structure is a 2D dynamic programming table or memoization cache keyed by indices (i, j). Each entry stores whether a prefix of the string matches a prefix of the pattern. This structure efficiently avoids recomputation of overlapping subproblems.
What is the time complexity of Regular Expression Matching?
The optimal solution runs in O(m*n) time where m is the length of the input string and n is the length of the pattern. Each state (i, j) representing a substring and subpattern pair is computed once. Space complexity is also O(m*n) for storing memoization or the DP table.

Ready to solve this problem?

Practice Regular Expression Matching with our built-in code editor and test cases.

Practice on FleetCode
Previous

Wildcard Matching