Regular Expression Matching — Editorial

Opening the reading…

Intuitionwhy every match can be described by two shorter prefixes

The match must cover all of s and all of p, so the useful question is not whether one character matches another in isolation. Ask whether the first i characters of s match the first j characters of p. Once that answer is known, a larger prefix can reuse it instead of exploring the same choices again.

A letter or a dot consumes exactly one character from each prefix. A star is different because it belongs to the preceding element: the pair before it can match zero characters, or it can match the current string character and remain available for another one. Those are the only two ways a star changes the prefixes, so they become the recurrence.

Let dp[i][j] mean that s[0..i-1] matches p[0..j-1]. For an ordinary matching token, use dp[i - 1][j - 1]. For a star, first try dp[i][j - 2], which skips the element and star entirely. If the element matches s[i - 1], also try dp[i - 1][j], which consumes one string character while keeping the star for future characters.

Approachfill prefix answers in dependency order

Create an (m + 1) by (n + 1) table, where m is the length of s and n is the length of p, so row i and column j describe prefixes whose lengths can be zero.

Set dp[0][0] to true because two empty prefixes match, and leave other entries false initially because a nonempty string cannot match an empty pattern.

Initialize the empty-string row separately. A pattern ending in a star can match empty only by discarding its preceding element and the star, so dp[0][j] inherits dp[0][j - 2].

For each non-star pattern character, copy dp[i - 1][j - 1] only when the character equals s[i - 1] or is a dot; otherwise the current prefixes cannot match.

For a star, begin with dp[i][j - 2], representing zero occurrences of its preceding element. Without this branch, patterns such as a* could never stop consuming.

If the character before the star matches s[i - 1], also combine dp[i - 1][j]. This consumes one string character but keeps the same star, allowing zero, one, or many occurrences through repeated transitions.

Return dp[m][n], not an answer for an intermediate cell, because the definition requires the entire string and the entire pattern to match.

Complexitythe table stores every pair of prefix lengths

MEASURE	BOUND	WHY
Time	O(mn)	The nested loops inspect each pair of nonempty prefixes once, and every cell performs only constant work: a character comparison and at most two table lookups. No pair of prefix lengths is recomputed.
Space	O(mn) extra space	The table keeps one boolean for every pair of prefix lengths. The returned boolean is required output and contributes no working memory. In the worst case, when both prefixes have their full lengths, all m + 1 by n + 1 cells are retained; there is no input shape that makes this bound larger.

Here m is the length of s and n is the length of p.

Annotated solutionC++ · bottom-up two-dimensional dynamic programming

CPPComplete bottom-up solution using prefix states and the two star transitions.

#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = static_cast<int>(s.size());
        int n = static_cast<int>(p.size());
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));

        dp[0][0] = true;

        for (int j = 1; j <= n; ++j) {
            if (p[j - 1] == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }

        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == s[i - 1] || p[j - 1] == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p[j - 1] == '*') {
                    dp[i][j] = dp[i][j - 2];

                    if (p[j - 2] == s[i - 1] || p[j - 2] == '.') {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                }
            }
        }

        return dp[m][n];
    }
};

The order inside the star branch carries the main insight. dp[i][j - 2] removes the star pair, while dp[i - 1][j] keeps the pair and consumes one matching character. The second transition must check p[j - 2], because the star itself is not the character being matched. Filling rows from small prefixes to large prefixes guarantees that both dependencies already exist.

The rolling-row alternativean O(n)-space optimisation when you do not need the full table

Each current cell reads only the previous row, the current row two columns earlier, and the previous-row value in the same column. That allows you to keep two one-dimensional rows instead of the full grid. This is a genuine space optimisation from O(mn) to O(n), while time remains O(mn); the tradeoff is that the complete prefix table is no longer available for debugging or reconstruction.

CPPRolling-row variant that preserves the same recurrence with O(n) extra space.

#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = static_cast<int>(s.size());
        int n = static_cast<int>(p.size());
        vector<bool> previous(n + 1, false);
        previous[0] = true;

        for (int j = 1; j <= n; ++j) {
            if (p[j - 1] == '*') {
                previous[j] = previous[j - 2];
            }
        }

        for (int i = 1; i <= m; ++i) {
            vector<bool> current(n + 1, false);

            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == s[i - 1] || p[j - 1] == '.') {
                    current[j] = previous[j - 1];
                } else if (p[j - 1] == '*') {
                    current[j] = current[j - 2];

                    if (p[j - 2] == s[i - 1] || p[j - 2] == '.') {
                        current[j] = current[j] || previous[j];
                    }
                }
            }

            previous.swap(current);
        }

        return previous[n];
    }
};