Regular Expression Matching

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

1. 1Create 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.
2. 2Set 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.
3. 3Initialize 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].
4. 4For 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.
5. 5For 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.
6. 6If 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.
7. 7Return 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

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

#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.

#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];
    }
};

Common mistakestwo wrong shapes that look plausible