LeetCode 10 – Regular Expression Matching

Regular Expression Matching is the first genuinely Hard problem on the list, and it earns it. The difficulty is not the code — the finished solution is twenty lines — it is that * does not mean what it looks like it means, and getting that wrong makes every subsequent decision wrong.

The problem

Implement matching for two metacharacters, over the entire input string, not a partial match:

. matches any single character.
* matches zero or more of the character immediately before it.

s = "aa",  p = "a"      -> false    the pattern must cover all of s
s = "aa",  p = "a*"     -> true     one 'a' repeated twice
s = "ab",  p = ".*"     -> true     any character, repeated
s = "aab", p = "c*a*b"  -> true     c* matches zero c's, a* matches "aa"
s = "",    p = "a*"     -> true     zero occurrences, so the pattern matches nothing

The one insight that unlocks it

* is not a character. It is a modifier on the character to its left, and the two of them are one indivisible unit: a*, .*, c*. This is not shell globbing, where * means "any run of anything" — a* matches "aaaa" and never matches "b".

Which means you never scan the pattern left to right one character at a time. At every position you must first look ahead one character to see whether a * follows, because that decides which of two completely different rules applies.

When p[j] is followed by a *, that unit can do one of two things, and you have to try both:

Zero occurrences. Skip the whole x* unit — jump the pattern forward by two, leave the string where it is.
One or more. Only possible if the current character matches (s[i] == p[j] or p[j] == '.'). Consume one character of the string and stay on the same pattern position, so the unit can be used again.

That "consume the string but not the pattern" step is what lets one a* absorb an arbitrarily long run. When there is no *, the rule is the simple one: the characters must match, and both indices advance by one.

Top-down: recursion, then a memo

Write the recursion first — it is a direct transcription of the rules above, and it is what you should put on the board before optimising anything.

private boolean dfs(String s, int i, String p, int j) {
    if (j == p.length()) return i == s.length();   // pattern spent: string must be too

    boolean firstMatches = i < s.length()
            && (p.charAt(j) == '.' || p.charAt(j) == s.charAt(i));

    if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
        return dfs(s, i, p, j + 2)                       // x* used zero times
            || (firstMatches && dfs(s, i + 1, p, j));   // x* used once more
    }
    return firstMatches && dfs(s, i + 1, p, j + 1);
}

Note the base case: reaching the end of the pattern is only a success if the string is also exhausted. Reaching the end of the string is not a failure — s = "" with p = "a*b*" still has to walk the pattern to prove every unit can match zero times.

This is exponential on inputs like s = "aaaaaaaaaaaaaaaaaaab", p = "a*a*a*a*a*b", because the same (i, j) pair is recomputed through many different paths. There are only m × n distinct pairs, so cache them. Use Boolean, not boolean, so null can mean "not computed yet" — with a primitive there is no way to distinguish an uncomputed cell from a computed false.

Bottom-up DP: the version to write

Same recurrence, no recursion. Let dp[i][j] mean "the first i characters of s match the first j characters of p". The offset-by-one indexing is deliberate: dp[0][0] is "empty matches empty", which is true, and it gives the empty-string cases somewhere to live.

The first row is the one people get wrong. dp[0][j] is not all false — an empty string genuinely matches "a*", "a*b*", ".*", and any other pattern made only of x* units. Seed it explicitly.

Java

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;   // empty matches empty

        // Empty string vs a pattern of x* units — each must take its zero-occurrence branch.
        for (int j = 2; j <= n; j++) {
            dp[0][j] = p.charAt(j - 1) == '*' && dp[0][j - 2];
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                char pc = p.charAt(j - 1);

                if (pc == '*') {
                    char prev = p.charAt(j - 2);                 // the char the * modifies
                    boolean zero = dp[i][j - 2];                 // drop the whole x* unit
                    boolean more = (prev == '.' || prev == s.charAt(i - 1))
                                 && dp[i - 1][j];                // consume s, reuse x*
                    dp[i][j] = zero || more;
                } else if (pc == '.' || pc == s.charAt(i - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                // otherwise dp[i][j] stays false
            }
        }

        return dp[m][n];
    }
}

p.charAt(j - 2) is safe without a bounds check because a well-formed pattern never begins with * — the problem guarantees every * has a preceding character. Say that out loud; an interviewer who was about to ask "what if the pattern is \"*a\"?" will be satisfied, and if they say the input is untrusted, add the guard.

Python

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True

        for j in range(2, n + 1):                       # empty string vs x* units
            dp[0][j] = p[j - 1] == '*' and dp[0][j - 2]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                pc = p[j - 1]
                if pc == '*':
                    prev = p[j - 2]
                    dp[i][j] = dp[i][j - 2] or (              # x* used zero times
                        (prev == '.' or prev == s[i - 1])     # x* used once more
                        and dp[i - 1][j]
                    )
                elif pc == '.' or pc == s[i - 1]:
                    dp[i][j] = dp[i - 1][j - 1]

        return dp[m][n]

Complexity

Approach	Time	Space
Plain recursion	exponential	`O(m + n)` stack
Recursion + memo	`O(m·n)`	`O(m·n)`
Bottom-up DP	`O(m·n)`	`O(m·n)`

The DP only ever reads row i - 1, so it rolls down to two rows and O(n) space. Offer that as the follow-up; do not write it first, because the two-row version is much harder to debug on a whiteboard.

How this differs from Wildcard Matching

Wildcard Matching (LeetCode 44) looks like the same problem and is not. There, * stands alone and matches any sequence of any characters, and ? matches exactly one. The DP table has the same shape, but the * branch changes: zero becomes dp[i][j - 1] (skip just the star, not a two-character unit) and the "consume one" branch has no preceding character to check against. Knowing which is which — and saying so — is a strong signal.

What the interviewer is checking

That you treat x* as one unit and look ahead for the *, rather than walking the pattern one character at a time.
That you try both the zero-occurrence and the one-or-more branch.
That s = "" against p = "a*b*" returns true — the first row of the table is the whole test.
That you spot the overlapping subproblems and memoise, instead of shipping the exponential recursion.
That you know the match must cover the entire string, not a prefix.