Regular Expression Matching

How it works

We want to check if s matches p, where:

• . matches any single character
• * means "zero or more of the previous character"

The usual bottom-up DP state is: dp[i][j] = does s[i:] match p[j:]?

A 2D table works, and a 1D array also works if we update carefully. This "optimal" version goes one step further: it updates the 1D array in-place without creating a second array.

The main challenge with in-place updates is that some transitions need the diagonal value:

• dp[i + 1][j + 1] (move both forward)

When we compress to 1D, that diagonal value would get overwritten while we move left through j. To handle this, we keep one extra variable (dp1) that stores the previous diagonal value as we update the row.

So at each (i, j) we can still access:

• dp[j] → old value for dp[i + 1][j]
• dp[j + 2] → current row value for skipping x*
• dp1 → old diagonal dp[i + 1][j + 1]

Steps

1. Create a 1D boolean array dp of size len(p) + 1:
   • dp[j] represents whether s[i + 1:] matches p[j:] for the current outer loop
2. Initialize the base case:
   • dp[len(p)] = true (empty pattern matches empty string at the end)
3. Iterate i from len(s) down to 0:
   • Save the old end value in dp1 (this will act as the diagonal when j moves left)
   • Update dp[len(p)] = (i == len(s)) since empty pattern only matches if string is also empty
4. Iterate j from len(p) - 1 down to 0:
   • Compute match:
     • true if i < len(s) and (s[i] == p[j] or p[j] == '.')
   • If the next pattern character is *:
     • Option 1: skip x* → use dp[j + 2]
     • Option 2: if match, consume one char from s and stay on j → use dp[j]
     • Combine both to get the result for dp[j]
   • Otherwise (no *):
     • If match, move both forward → result is the diagonal dp1
   • Update dp[j] with the computed result
   • Shift the diagonal tracker:
     • set dp1 to the old dp[j] value before it was overwritten
5. After all updates, dp[0] represents whether s[0:] matches p[0:]
6. Return dp[0]

Complexity

• Time complexity: O(m * n)
• Space complexity: O(n)

Where m is the length of the string s and n is the length of the string p.

Things to watch for

Misunderstanding How Star Works

The * character means "zero or more of the preceding element," not "zero or more of any character." A common mistake is treating a* as matching any sequence of characters. In reality, a* only matches zero or more 'a' characters. Similarly, .* matches zero or more of any single character (because . matches any character).

Forgetting That Star Can Match Zero Occurrences

When encountering x* in the pattern, many solutions only consider the case where x matches at least one character. However, x* can also match zero characters, meaning the entire x* portion can be skipped. Both branches must be explored: skip x* entirely or consume a matching character while staying on the same pattern position.

Off-by-One Errors When Checking for Star

The pattern must be checked carefully to see if the next character is *. A common bug is checking p[j] instead of p[j+1] for the star, or failing to verify that j+1 is within bounds before accessing it. This leads to index out of bounds errors or incorrect pattern matching logic.

Not Handling Empty String or Pattern Edge Cases

The base cases require careful handling. When the pattern is exhausted (j == n), the match is valid only if the string is also exhausted (i == m). However, when the string is exhausted but the pattern is not, matching can still succeed if the remaining pattern consists entirely of x* pairs. Failing to account for patterns like a*b*c* matching an empty string is a common oversight.

Incorrect DP State Transitions

In the bottom-up DP approach, the iteration order matters. Processing from the end of both strings toward the beginning ensures that required subproblem solutions are available. A common mistake is iterating in the wrong direction or incorrectly referencing dp[i+1][j+1] when it has not been computed yet.

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        dp = [False] * (len(p) + 1)
        dp[len(p)] = True

        for i in range(len(s), -1, -1):
            dp1 = dp[len(p)]
            dp[len(p)] = (i == len(s))

            for j in range(len(p) - 1, -1, -1):
                match = i < len(s) and (s[i] == p[j] or p[j] == ".")
                res = False
                if (j + 1) < len(p) and p[j + 1] == "*":
                    res = dp[j + 2]
                    if match:
                        res |= dp[j]
                elif match:
                    res = dp1
                dp[j], dp1 = res, dp[j]

        return dp[0]

class Solution {
public:
    bool isMatch(string s, string p) {
        vector<bool> dp(p.length() + 1, false);
        dp[p.length()] = true;

        for (int i = s.length(); i >= 0; i--) {
            bool dp1 = dp[p.length()];
            dp[p.length()] = (i == s.length());

            for (int j = p.length() - 1; j >= 0; j--) {
                bool match = i < s.length() &&
                             (s[i] == p[j] || p[j] == '.');
                bool res = false;
                if (j + 1 < p.length() && p[j + 1] == '*') {
                    res = dp[j + 2];
                    if (match) {
                        res = res || dp[j];
                    }
                } else if (match) {
                    res = dp1;
                }
                dp1 = dp[j];
                dp[j] = res;
            }
        }

        return dp[0];
    }
};