Regular Expression Matching

LeetCode 10: Regular Expression Matching Solution & Explanation

Problem Overview

TL;DR: Use a two-dimensional dynamic programming table to determine whether every prefix of s can be matched by every prefix of p, handling * through its zero-occurrence and one-or-more-occurrence transitions.

The LeetCode 10 Solution determines whether the entire string s matches the entire pattern p. A lowercase letter matches itself, . matches any single character, and * allows the preceding element to appear zero or more times.

This is a popular interview question because it tests state design, boundary handling, and dynamic programming over two strings. The result must describe a complete match: matching only a prefix of s is not sufficient.

Brute Force Approach for Regular Expression Matching

A direct recursive solution explores every valid interpretation of *.

At a state (i, j):

• i represents the current position in s.
• j represents the current position in p.
• If the current pattern element is followed by *, there are two choices:
  1. Skip the element and *, treating it as occurring zero times.
  2. If the current characters match, consume one character from s while keeping the pattern position unchanged.
• Otherwise, consume one character from both strings when they match.

Naive Pseudocode

match(i, j):
    if j == length(p):
        return i == length(s)

    firstMatch =
        i < length(s) and
        (p[j] == '.' or p[j] == s[i])

    if j + 1 < length(p) and p[j + 1] == '*':
        return match(i, j + 2) or
               (firstMatch and match(i + 1, j))

    return firstMatch and match(i + 1, j + 1)

The recursive calls can repeatedly evaluate the same (i, j) state. For example, patterns containing several * symbols can produce many different recursion paths that converge on identical string and pattern positions.

Complexity of the Brute Force Method

In the worst case, the recursion tree has exponential size. Its time complexity can reach:

O(2^(n + m))

where n = s.length() and m = p.length().

Although the constraints are small, this repeated work makes the naive approach inefficient and vulnerable to Time Limit Exceeded on adversarial inputs. The repeated (i, j) states are the reason to use a two-dimensional DP table.

Algorithm Strategy: Dynamic Programming (DP) Patterns

Maintain a two-dimensional boolean table whose dimensions correspond to positions in the string and pattern.

The verified implementations use two equivalent orientations:

• The C++ implementation builds answers for prefixes:
  • dp[i][j] means the first i characters of s match the first j characters of p.
• The Java and Python implementations build answers for suffixes:
  • dp[i][j] means the suffix beginning at pattern position i matches the suffix beginning at string position j.

For a * transition:

• The zero-occurrence option skips the preceding pattern element and *.
• The repeated-occurrence option consumes one string character if the preceding element matches, while keeping the * state active.

For a regular character or ., the current elements must match, and the state advances diagonally.

The table initialization must account for empty strings. A pattern such as q* can match an empty string because the * group may be skipped.

Execution Flow

1. Represent the current matching problem using two indices: one for s and one for p.
2. Initialize the base case where both sides are empty:
   • An empty string matches an empty pattern.
3. Handle patterns that can match an empty string:
   • A character followed by * can be skipped.
   • This behavior may repeat across multiple * groups.
4. For each state, determine whether the current pattern element matches the current string character:
   • A literal matches the same literal.
   • . matches any available lowercase character.
5. If the next pattern symbol is *:
   • Transition past the pair for zero occurrences.
   • If the current element matches, consume one string character and remain at the same pattern element.
6. If the current pattern element is not part of a * group:
   • Require a current-character match.
   • Advance both positions.
7. Return the state representing the complete string and complete pattern:
   • In the C++ prefix table, this is dp[n][m].
   • In the Java and Python suffix tables, this is dp[0][0].

Proof of Correctness

We prove that the DP result is true exactly when the corresponding string and pattern portions match completely.

Base Case

When both the string portion and pattern portion are empty, the match is valid. The table records this state as true.

If the string portion is empty and the remaining pattern consists of groups such as x*, each group can represent zero occurrences. The initialization or transitions therefore correctly mark such states as matchable.

Ordinary Character or .

If the current pattern element is not followed by *, it must consume exactly one string character.

• A literal is valid only when it equals the current string character.
• . is valid for any current string character.

When the characters match, the algorithm relies on the state for the remaining portions. By the induction hypothesis, that remaining state is true exactly when the rest of the strings match.

* Transition

For a group consisting of an element followed by *, every valid match must use one of two possibilities:

1. The element occurs zero times. The algorithm skips both the element and *.
2. The element occurs at least once. The current element must match the current string character, and the algorithm consumes that character while keeping the same * group available for additional occurrences.

These two transitions cover all valid interpretations of *. Since both transitions use smaller remaining portions or a shorter remaining string, their stored results are correct by induction.

Complete Match

The returned state represents the entire string and entire pattern, not merely a prefix. Therefore, the algorithm returns true exactly when all characters of s are consumed by all valid pattern elements of p.

Pattern Reuse Notes

The following problems share the same pattern/subpattern:

• LeetCode 583: Delete Operation for Two Strings
• LeetCode 72: Edit Distance
• LeetCode 712: Minimum ASCII Delete Sum for Two Strings

Each problem uses a two-dimensional DP table whose state is defined by positions in two strings. The transition meaning changes:

• Delete Operation for Two Strings minimizes deletions.
• Edit Distance combines insertion, deletion, and replacement costs.
• Minimum ASCII Delete Sum minimizes the total deletion value.

Regular Expression Matching stores boolean feasibility instead of a minimum cost, but the two-dimensional state organization is the same.

Reference Implementation

C++ Solution for LeetCode 10

1class Solution {
2public:
3    bool isMatch(string s, string p) {
4        int n = s.size();
5        int m = p.size();
6        vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));
7        dp[0][0] = true;
8
9        for (int j = 2; j <= m; ++j) {
10            if (p[j - 1] == '*') {
11                dp[0][j] = dp[0][j - 2];
12            }
13        }
14
15        for (int i = 1; i <= n; ++i) {
16            for (int j = 1; j <= m; ++j) {
17                if (p[j - 1] == '*') {
18                    dp[i][j] = dp[i][j - 2];
19
20                    char preceding = p[j - 2];
21                    if (preceding == '.' || preceding == s[i - 1]) {
22                        dp[i][j] = dp[i][j] || dp[i - 1][j];
23                    }
24                } else if (p[j - 1] == '.' || p[j - 1] == s[i - 1]) {
25                    dp[i][j] = dp[i - 1][j - 1];
26                }
27            }
28        }
29
30        return dp[n][m];
31    }
32};

The C++ table uses prefix lengths. When p[j - 1] is *, dp[i][j - 2] represents zero occurrences, while dp[i - 1][j] represents consuming one matching string character and keeping the * group active.

Java Solution for LeetCode 10

1class Solution {
2    public boolean isMatch(String s, String p) {
3        int sLen = s.length();
4        int pLen = p.length();
5        boolean[][] dp = new boolean[pLen + 1][sLen + 1];
6        dp[pLen][sLen] = true;
7
8        for (int i = pLen - 1; i >= 0; i--) {
9            for (int j = sLen; j >= 0; j--) {
10                boolean firstMatch = j < sLen && (p.charAt(i) == '.' || p.charAt(i) == s.charAt(j));
11
12                if (i + 1 < pLen && p.charAt(i + 1) == '*') {
13                    dp[i][j] = dp[i + 2][j] || (firstMatch && dp[i][j + 1]);
14                } else {
15                    dp[i][j] = firstMatch && dp[i + 1][j + 1];
16                }
17            }
18        }
19
20        return dp[0][0];
21    }
22}

The Java implementation uses suffix states. dp[i][j] describes whether the remaining pattern beginning at i matches the remaining string beginning at j.

For a * group:

• dp[i + 2][j] skips the group.
• dp[i][j + 1] consumes one matching string character and keeps the group available.

Python Solution for LeetCode 10

1class Solution:
2    def isMatch(self, s: str, p: str) -> bool:
3        s_len = len(s)
4        p_len = len(p)
5        dp = [[False] * (s_len + 1) for _ in range(p_len + 1)]
6        dp[p_len][s_len] = True
7
8        for i in range(p_len - 1, -1, -1):
9            for j in range(s_len, -1, -1):
10                first_match = j < s_len and (p[i] == '.' or p[i] == s[j])
11
12                if i + 1 < p_len and p[i + 1] == '*':
13                    dp[i][j] = dp[i + 2][j] or (first_match and dp[i][j + 1])
14                else:
15                    dp[i][j] = first_match and dp[i + 1][j + 1]
16
17        return dp[0][0]

The Python implementation follows the same suffix-based state definition as the Java version. The reverse iteration ensures that every state referenced by the current cell has already been computed.