AlgoMaster Logo

Regular Expression Matching

hardFrequencyUpdated September 21, 2026

Understanding the Problem

We need to check whether a string s fully matches a pattern p that supports two special characters. The dot '.' is a wildcard that matches any single character, which is straightforward. The tricky part is '*', which doesn't stand alone. It modifies the character right before it, meaning "match that previous character zero or more times."

So a* could match "", "a", "aa", "aaa", and so on. And .* could match any string of any length, because '.' matches any character and '*' lets you repeat it as many times as needed.

A few things make this problem challenging. First, '*' can mean "zero occurrences" of the preceding character. This means a*b matches "b", because we use zero a's. Second, we need to consider multiple ways to consume the pattern. When we see a*, should we use it to match zero a's and move past it, or match one a and keep it available for more? This branching creates overlapping subproblems, which is the classic signal for dynamic programming.

Key Constraints:

  • s.length <= 20 and p.length <= 20 → The inputs are small. Even an exponential brute force runs in time here, but the O(n * m) DP is the solution to aim for.
  • s contains only lowercase English letters → No special characters in the input string, only in the pattern.
  • Every '*' has a valid preceding character → We don't need to handle edge cases like * appearing first or two * in a row.

Approach 1: Recursive Brute Force

Intuition

We can match the two strings character by character from the front. Start at the beginning of both strings and ask whether the current characters match, then handle what comes after.

When no '*' is involved, this is direct. If the current pattern character matches the current string character (either they are the same letter, or the pattern has '.'), we move both pointers forward and check the rest.

The '*' case is where the branching comes from. When the next character in the pattern is '*', we have a choice. We can skip the x* pair entirely, which matches zero occurrences and moves the pattern pointer forward by 2 while leaving the string pointer unchanged. Or, if the current characters match, we can consume one character from the string and keep the x* pattern in place for further matches.

This branching creates a recursion tree that can explore many paths, but with strings of length 20, it's manageable.

Algorithm

  1. If the pattern is empty, return true only if the string is also empty.
  2. Check if the first characters match: the string is non-empty and the pattern's first character is either the same letter or a dot.
  3. If the pattern has at least 2 characters and the second character is '*':
    • Try skipping the x* pair (zero matches): recurse with the same string and pattern advanced by 2.
    • If the first characters match, try consuming one string character: recurse with the string advanced by 1 and the same pattern.
    • Return true if either path succeeds.
  4. If there's no '*' involved, and the first characters match, recurse on both advanced by 1.
  5. Otherwise, return false.

Visualization and Code

Loading animation...

The brute force re-solves the same subproblems repeatedly. Different matching decisions can lead to the same (i, j) state, and the recursion recomputes that state from scratch each time. Caching each (i, j) result on first computation removes the repeated work.

Approach 2: Recursion with Memoization (Top-Down DP)

Intuition

The brute force has the right logic, but it's wasteful. The state of our recursion can be fully described by two numbers: how far we've consumed into s (index i) and how far we've consumed into p (index j). There are only (n+1) * (m+1) possible (i, j) pairs. If we store the result the first time we compute each pair, we never redo work.

This is classic memoization. We keep the exact same recursive logic from Approach 1, but add a cache. Before computing the answer for (i, j), we check if we've already solved it. If so, return the cached result. If not, compute it, cache it, and return.

Algorithm

  1. Create a memo table (2D array or hash map) initialized to "not computed."
  2. Define a recursive function dp(i, j) that returns whether s[i..] matches p[j..].
  3. If (i, j) is already in the memo, return the cached value.
  4. Base case: if j == m, return i == n (pattern exhausted, string must be too).
  5. Compute firstMatch: i < n and (s[i] == p[j] or p[j] == '.').
  6. If j + 1 < m and p[j+1] == '*':
    • Result = dp(i, j+2) OR (firstMatch AND dp(i+1, j)).
  7. Otherwise: result = firstMatch AND dp(i+1, j+1).
  8. Store result in memo and return it.

Visualization and Code

Loading animation...

The memoized solution is already O(n * m) in time, but it relies on recursion and its call-stack overhead. The next approach fills the same table iteratively from the base case outward, removing the recursion.

Approach 3: Bottom-Up Dynamic Programming

Intuition

Instead of starting from (0, 0) and recursing deeper, we flip the direction. We build a 2D table where dp[i][j] answers: "does s[i..] match p[j..]?" We start from the bottom-right corner (both strings exhausted) and fill the table backward.

The recurrence is identical to what we had in the memoized version. The only difference is the order of computation. By filling the table from i = n down to 0 and j = m down to 0, we ensure that when we compute dp[i][j], all the cells it depends on (dp[i][j+2], dp[i+1][j], dp[i+1][j+1]) are already filled in.

The base cases need some care. dp[n][m] = true because empty string matches empty pattern. But we also need to handle the case where the string is exhausted but the pattern still has x* pairs that can match zero characters. For example, s = "" and p = "a*b*c*" should return true, because every x* can match zero times.

Algorithm

  1. Create a 2D boolean array dp of size (n+1) x (m+1), initialized to false.
  2. Set dp[n][m] = true (both strings exhausted).
  3. Fill in the last row: for j from m-1 down to 0, dp[n][j] is true only if p[j+1] == '*' and dp[n][j+2] is true (pattern has x* pairs that all match zero times).
  4. For i from n-1 down to 0, for j from m-1 down to 0:
    • Compute firstMatch = (s[i] == p[j] || p[j] == '.').
    • If j+1 < m and p[j+1] == '*': dp[i][j] = dp[i][j+2] || (firstMatch && dp[i+1][j]).
    • Else: dp[i][j] = firstMatch && dp[i+1][j+1].
  5. Return dp[0][0].

Visualization and Code

Loading animation...