What is the time complexity of Regular Expression Matching?

The optimal solution has a time complexity of O(mn).

What data structures are used to solve Regular Expression Matching?

This problem uses String, Dynamic Programming, Recursion. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Regular Expression Matching?

Insight 1: The core idea is to use dynamic programming to store and reuse results of subproblems, which greatly improves efficiency compared to a naive recursive approach. Insight 2: The '*' character presents two main scenarios: it can match zero occurrences of the preceding character (effectively skipping that part of the pattern), or it can match one or more occurrences (consuming characters from the string and keeping the same position in the pattern).

Which companies ask LeetCode 10. Regular Expression Matching in interviews?

This problem is frequently asked at Airbnb, Amazon, Apple, Bloomberg, ByteDance and 17 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Regular Expression Matching - LeetCode 10 Solution

Regular Expression Matching - Complete Solution Guide

Regular Expression Matching is LeetCode problem 10, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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

Detailed Explanation

The problem asks us to implement regular expression matching with support for two special characters: '.' and '*'. The '.' character matches any single character, and the '*' character matches zero or more occurrences of the preceding character. The matching should cover the entire input string, meaning a partial match is not sufficient. We are given an input string 's' and a pattern 'p', and we must return true if the pattern matches the string, and false otherwise.

Solution Approach

The provided code uses a top-down dynamic programming approach with memoization to solve the regular expression matching problem. A recursive function `dp(i, j)` is defined to determine if the substring of `s` starting at index `i` matches the substring of `p` starting at index `j`. The memoization table `memo` stores the results of previous calls to `dp(i, j)` to avoid redundant computations. The function handles base cases where either the string or pattern (or both) is exhausted, as well as the two cases for the '*' character.

Step-by-Step Algorithm

Step 1: Define a recursive function `dp(i, j)` that takes the starting indices `i` for the string `s` and `j` for the pattern `p` as input. This function returns `true` if `s[i:]` matches `p[j:]` and `false` otherwise.
Step 2: Check the base case: if `j` reaches the end of `p`, then the match is successful only if `i` also reaches the end of `s`.
Step 3: Check if the result for the current `(i, j)` pair is already memoized in the `memo` table. If so, return the stored value.
Step 4: Determine if the first characters of the current substrings match. This is true if `s[i]` and `p[j]` are equal, or if `p[j]` is a '.', and `i` is within the bounds of `s`.
Step 5: If the next character in `p` after `p[j]` is a '*', handle the two cases it represents:
- Case 1: The '*' matches zero occurrences of the preceding character. In this case, skip the 'char*' part of the pattern and recursively call `dp(i, j + 2)`.
- Case 2: The '*' matches one or more occurrences of the preceding character. This requires a `first_match` and then advance in the string while staying at the same pattern index `dp(i + 1, j)`.
- The result is true if either of these cases is true.
Step 6: If the next character in `p` is not a '*', then it's a standard one-to-one character match. The match is successful only if `first_match` is true, and the remaining substrings also match. Recursively call `dp(i + 1, j + 1)`.
Step 7: Store the result in the `memo` table before returning it.
Step 8: The initial call to `dp(0, 0)` starts the matching process from the beginning of both `s` and `p`.

Key Insights

Insight 1: The core idea is to use dynamic programming to store and reuse results of subproblems, which greatly improves efficiency compared to a naive recursive approach.
Insight 2: The '*' character presents two main scenarios: it can match zero occurrences of the preceding character (effectively skipping that part of the pattern), or it can match one or more occurrences (consuming characters from the string and keeping the same position in the pattern).
Insight 3: Memoization is crucial for optimizing the recursive solution. Without it, the same subproblems are repeatedly solved, leading to exponential time complexity. The problem constraints on string length (up to 20) also hint towards a dynamic programming solution, as a purely recursive approach would likely time out.

Complexity Analysis

Time Complexity: O(mn)

Space Complexity: O(mn)

Topics

This problem involves: String, Dynamic Programming, Recursion.

Companies

Asked at: Airbnb, Amazon, Apple, Bloomberg, ByteDance, Citadel, Confluent, Coupang, Hiver, MakeMyTrip, Meta, Microsoft, Oracle, Snowflake, TikTok, Turing, Uber, WinZO, WorldQuant, X, Yahoo, Zoho.

Regular Expression Matching | LeetCode 10

Hard

String Dynamic Programming Recursion

Time: O(mn)Space: O(mn)

Solution Code

Available in:

class Solution {
    public boolean isMatch(String s, String p) {
        // Use a HashMap to store the memoized results.
        java.util.HashMap<String, Boolean> memo = new java.util.HashMap<>();

        // Define the recursive helper function.
        return dp(0, 0, s, p, memo);
    }

    private boolean dp(int i, int j, String s, String p, java.util.HashMap<String, Boolean> memo) {
        // Create a unique key for the current state (i, j).
        String key = i + "," + j;

        // If the result is already memoized, return it.
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        // Base case: If the pattern is exhausted, the string must also be exhausted.
        if (j == p.length()) {
            return i == s.length();
        }

        // Check if the first character matches.
        boolean first_match = i < s.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.');

        boolean res;
        if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
            // Case 1: '*' matches zero occurrences of the preceding element.
            // We skip the 'char*' part of the pattern.
            // Case 2: '*' matches one or more occurrences.
            // This requires a match at the current position, then we advance
            // in the string but stay at the same pattern position.
            res = dp(i, j + 2, s, p, memo) || (first_match && dp(i + 1, j, s, p, memo));
        } else {
            // No '*' follows, so it's a standard one-to-one character match.
            res = first_match && dp(i + 1, j + 1, s, p, memo);
        }

        // Memoize the result and return it.
        memo.put(key, res);
        return res;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 10: Regular Expression Matching - Detailed explanation and solution approaches.

Topics

String Dynamic Programming Recursion

Companies

AirbnbAmazonAppleBloombergByteDanceCitadelConfluentCoupang

Stats

Difficulty:Hard

Languages:4

Companies:22

Problem #:10

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

11 steps

1
Step 1: Define a recursive function `dp(i, j)` that takes the starting indices `i` for the string `s` and `j` for the pattern `p` as input. This function returns `true` if `s[i:]` matches `p[j:]` and `false` otherwise.
2
Step 2: Check the base case: if `j` reaches the end of `p`, then the match is successful only if `i` also reaches the end of `s`.
3
Step 3: Check if the result for the current `(i, j)` pair is already memoized in the `memo` table. If so, return the stored value.
4
Step 4: Determine if the first characters of the current substrings match. This is true if `s[i]` and `p[j]` are equal, or if `p[j]` is a '.', and `i` is within the bounds of `s`.
5
Step 5: If the next character in `p` after `p[j]` is a '*', handle the two cases it represents:
6
- Case 1: The '*' matches zero occurrences of the preceding character. In this case, skip the 'char*' part of the pattern and recursively call `dp(i, j + 2)`.
7
- Case 2: The '*' matches one or more occurrences of the preceding character. This requires a `first_match` and then advance in the string while staying at the same pattern index `dp(i + 1, j)`.
8
- The result is true if either of these cases is true.
9
Step 6: If the next character in `p` is not a '*', then it's a standard one-to-one character match. The match is successful only if `first_match` is true, and the remaining substrings also match. Recursively call `dp(i + 1, j + 1)`.
10
Step 7: Store the result in the `memo` table before returning it.
11
Step 8: The initial call to `dp(0, 0)` starts the matching process from the beginning of both `s` and `p`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(mn)

💾

Space Complexity

O(mn)

📝

Why?

The time complexity is O(mn) because the dp function is called at most once for each pair of (i, j) indices, where i ranges from 0 to s.length() and j ranges from 0 to p.length(). The space complexity is O(mn) because the memoization table stores the results of each dp(i, j) call, and the size of the memoization table is proportional to the product of the lengths of s and p.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Bottom-up Dynamic Programming

A bottom-up approach builds the DP table iteratively, starting from the base cases. It fills the table based on the same logic as the recursive solution, but avoids recursion overhead.

Time: O(mn)Space: O(mn)

Trade-offs: The bottom-up approach avoids the overhead of recursive calls, which can be beneficial for performance in some cases. However, the top-down approach with memoization can be more intuitive to understand and implement for some developers.

✨

Key Insights

1Insight 1: The core idea is to use dynamic programming to store and reuse results of subproblems, which greatly improves efficiency compared to a naive recursive approach.
2Insight 2: The '*' character presents two main scenarios: it can match zero occurrences of the preceding character (effectively skipping that part of the pattern), or it can match one or more occurrences (consuming characters from the string and keeping the same position in the pattern).
3Insight 3: Memoization is crucial for optimizing the recursive solution. Without it, the same subproblems are repeatedly solved, leading to exponential time complexity. The problem constraints on string length (up to 20) also hint towards a dynamic programming solution, as a purely recursive approach would likely time out.

📚

Key Terms Explained

For Students

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

Recursion

A function that calls itself to solve smaller versions of the same problem.

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Empty string 's' and empty pattern 'p'. The solution correctly handles this base case in the recursive function. If p is empty, the match is true only when s is also empty.
Edge case 2: Pattern with multiple consecutive '*' characters. The problem statement guarantees that '*' always follows a valid character, so this scenario is handled by the logic related to the '*' character. Specifically, it decides whether to ignore the preceding character and '*' or attempt to match one or more occurrences.
Edge case 3: The pattern contains '.*'. This will match any string because '.' matches any character and '*' matches zero or more occurrences of it.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Incorrectly handling the '*' character. Forgetting to consider both cases where the '*' matches zero occurrences and where it matches one or more occurrences can lead to incorrect results.

✗Common mistake 2: Failing to memoize the results of subproblems. Without memoization, the solution becomes exponential and will likely time out for larger inputs.

✗Common mistake 3: Not handling the base cases correctly. Especially the situation when the pattern is exhausted.

✗Common mistake 4: Assuming the constraints are weak and trying to solve with backtracking instead of dynamic programming, which inevitably leads to timeouts.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Text editors and IDEs use regular expression matching for features like search and replace.

🏦Real-world scenario 2: Network security systems use regular expressions to detect malicious patterns in network traffic, such as intrusions or malware signatures.

🎮Real-world scenario 3: Data validation: Regular expressions are used to validate the format of user input, such as email addresses or phone numbers.

📱Real-world scenario 4: Parsing and compiling: Compilers and interpreters use regular expressions as part of lexical analysis to identify keywords, operators, and other language elements.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

String problems often involve sliding windows or two pointers. Consider if the character set is limited (lowercase letters = only 26 possibilities).

🎯 Interview Tip

It's okay to not finish hard problems in interviews. Show your problem-solving process.

⚠️ Watch Out

Mutating strings directly in languages where strings are immutable. Use StringBuilder or arrays.

👨‍💻 From Experience

I encountered a variation of this problem in a system design interview. The key was recognizing the underlying pattern.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 11, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 13

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 6

❓

Frequently Asked Questions

How do I handle string manipulation efficiently?

In languages with immutable strings (Java, Python, C#), use StringBuilder/list to avoid O(n) concatenation cost. Consider using character arrays for in-place modifications. For pattern matching, consider KMP or Rabin-Karp for O(n+m) complexity.

How do I identify if a problem needs dynamic programming?

DP problems typically have: 1) Overlapping subproblems (same calculation repeated), 2) Optimal substructure (optimal solution uses optimal solutions to subproblems). Look for keywords like "minimum/maximum," "count ways," "is it possible," or "longest/shortest."

How do I approach hard algorithm problems?

Hard problems often require: 1) Breaking down into subproblems, 2) Combining multiple advanced techniques, 3) Careful optimization of brute force. Start with a working solution (even O(n²) or worse), then optimize. Draw examples, identify patterns, and think about what makes this problem unique.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Regular Expression Matching"?

For this hard-level String problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether dynamic programming techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?