Scale Engineer

Regular Expression Matching

Hard
#0010Time: O((S+P) * 2^(S+P/2))Space: O(S + P)22 companies
Patterns
RecursionDynamic Programming
Data structures
String
Companies
AirbnbAmazonAppleBloomberg

Prompt

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.

Approaches

3 approaches with complexity analysis and trade-offs.

A straightforward recursive approach that directly translates the problem definition into a recursive function. It explores all possible matching paths without memoization, leading to redundant computations for the same subproblems.

Algorithm

  1. Define a recursive function isMatch(s, p).
  2. Base Case: If p is empty, return true if s is also empty, otherwise false.
  3. Let first_match be true if s is not empty and its first character matches p's first character (or p's first character is '.').
  4. If p has length >= 2 and its second character is *:
    • Return isMatch(s, p.substring(2)) (treating x* as zero occurrences) OR (first_match AND isMatch(s.substring(1), p)) (treating x* as one or more occurrences).
  5. Otherwise (no *):
    • Return first_match AND isMatch(s.substring(1), p.substring(1)).

Walkthrough

The core idea is to define a function isMatch(text, pattern) that checks if the text matches the pattern. The recursion proceeds by considering the first characters of the current text and pattern.

  • Base Case: If the pattern is empty, the text must also be empty for a match.
  • Recursive Step:
    • We check if the first character of the text matches the first character of the pattern (or if the pattern character is '.').
    • If the second character of the pattern is *:
      • We have two choices:
        1. The * matches zero preceding elements. We skip this part of the pattern (pattern.substring(2)) and see if it matches the current text.
        2. The * matches one or more preceding elements. This is only possible if the first characters match. If they do, we move to the next character in the text (text.substring(1)) and try to match it against the same pattern (since * can match multiple characters).
      • The result is true if either choice leads to a match.
    • If the second character is not *:
      • We must have a match of the first characters. If so, we recursively call the function for the rest of the text and pattern (text.substring(1), pattern.substring(1)).

This approach suffers from re-calculating the same subproblems multiple times, leading to exponential time complexity in the worst case.

class Solution {    public boolean isMatch(String s, String p) {        if (p.isEmpty()) {            return s.isEmpty();        }        boolean firstMatch = (!s.isEmpty() &&                              (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.'));         if (p.length() >= 2 && p.charAt(1) == '*') {            // Case 1: '*' matches zero preceding element            // Case 2: '*' matches one or more preceding element            return (isMatch(s, p.substring(2)) ||                    (firstMatch && isMatch(s.substring(1), p)));        } else {            // No '*'            return firstMatch && isMatch(s.substring(1), p.substring(1));        }    }}

Complexity

Time

O((S+P) * 2^(S+P/2))

Space

O(S + P)

Trade-offs

Pros

  • Simple to understand and implement directly from the problem's recursive definition.

Cons

  • Extremely inefficient due to re-computation of overlapping subproblems.

  • Can lead to a "Time Limit Exceeded" error on many platforms for non-trivial inputs.

Solutions

public class Solution {    public bool IsMatch(string s, string p) {        int m = s.Length, n = p.Length;        bool[, ] f = new bool[m + 1, n + 1];        f[0, 0] = true;        for (int i = 0; i <= m; ++i) {            for (int j = 1; j <= n; ++j) {                if (p[j - 1] == '*') {                    f[i, j] = f[i, j - 2];                    if (i > 0 && (p[j - 2] == '.' || p[j - 2] == s[i - 1])) {                        f[i, j] |= f[i - 1, j];                    }                } else if (i > 0 && (p[j - 1] == '.' || p[j - 1] == s[i - 1])) {                    f[i, j] = f[i - 1, j - 1];                }            }        }        return f[m, n];    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem