121.Regular Expression Matching

Hard2-D Dynamic Programming · 11/11

Problem

Given an input string s and a pattern p, implement regular-expression matching with support for two special characters:

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

The match must cover the entire input string, not just part of it.

Examples

Input:  s = "aa", p = "a"
Output: false
Explanation: "a" matches only one character; s has two.

Input:  s = "aa", p = "a*"
Output: true
Explanation: '*' repeats 'a' twice.

Input:  s = "ab", p = ".*"
Output: true
Explanation: ".*" means zero or more of any character.

Input:  s = "aab", p = "c*a*b"
Output: true
Explanation: "c*" matches zero 'c's, "a*" matches "aa", then 'b' matches 'b'.

Constraints

1 <= s.length <= 20
1 <= p.length <= 20
s contains only lowercase English letters.
p contains only lowercase English letters, '.', and '*'.
Every '*' is preceded by a valid character to repeat.

💡 Key Insight

Treat x* as one token. Let match(i, j) mean "s[i..] matches p[j..]" and let first = i < m && (p[j] == s[i] || p[j] == '.').

If p[j + 1] == '*': either use the star zero times — skip the token, match(i, j + 2) — or use it once more — consume one char of s and stay on the same token, first && match(i + 1, j).
Otherwise: first && match(i + 1, j + 1).

The state is (i, j), so the problem is a DP on an (m+1) x (n+1) table, and each row depends only on the row below it.

Recursion (Brute Force)

TimeExponential in the worst caseSpaceO(m + n)

Intuition

Directly implement the rule above. The * case creates two branches (zero vs. one-more), which is where the exponential blow-up comes from.

Algorithm

match(i, j):
- If j == n, return i == m (pattern used up; string must be too).
- first = i < m && (p[j] == s[i] || p[j] == '.').
- If j + 1 < n && p[j + 1] == '*': return match(i, j + 2) || (first && match(i + 1, j)).
- Else return first && match(i + 1, j + 1).
Return match(0, 0).

Visualization

flowchart TD
    A["match(0,0)<br/>s='aab' p='c*a*b'"] -->|"c* zero times"| B["match(0,2)<br/>p='a*b'"]
    A -->|"c* once: 'a' != 'c'"| X["fail"]
    B -->|"a* once: consume 'a'"| C["match(1,2)"]
    B -->|"a* zero"| D["match(0,4)<br/>'b' vs 'a' fail"]
    C -->|"a* once: consume 'a'"| E["match(2,2)"]
    C -->|"a* zero"| F["match(1,4) fail"]
    E -->|"a* zero"| G["match(2,4)<br/>'b' == 'b'"]
    G --> H["match(3,5) = true"]

Code

java

class Solution {
    public boolean isMatch(String s, String p) {
        return match(s, p, 0, 0);
    }

    private boolean match(String s, String p, int i, int j) {
        if (j == p.length()) {
            return i == s.length(); // pattern exhausted
        }
        boolean first = i < s.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.');
        if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
            // skip "x*" entirely, or use it for one char and stay on it
            return match(s, p, i, j + 2) || (first && match(s, p, i + 1, j));
        }
        return first && match(s, p, i + 1, j + 1);
    }
}

Complexity

Time: Exponential in the worst case — e.g. s = "aaaaaaaaaaaaab", p = "a*a*a*a*a*c" explores every way to split the as among the stars.
Space: O(m + n) — recursion depth.

Top-Down Memoization

TimeO(m · n)SpaceO(m · n)

Intuition

The result of match(i, j) never changes, and there are only (m + 1) · (n + 1) pairs. Cache them in a Boolean[][].

Algorithm

memo = new Boolean[m + 1][n + 1].
Same recursion; check and fill the cache.

Dry Run

s = "aa", p = "a*"
match(0,0): star → match(0,2)=false (i≠m) || (first && match(1,0))
match(1,0): star → match(1,2)=false || (first && match(2,0))
match(2,0): star → match(2,2)=true   ✓ cached
→ match(1,0) = true → match(0,0) = true

Code

java

class Solution {
    private Boolean[][] memo;
    private String s, p;

    public boolean isMatch(String s, String p) {
        this.s = s;
        this.p = p;
        memo = new Boolean[s.length() + 1][p.length() + 1];
        return match(0, 0);
    }

    private boolean match(int i, int j) {
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        boolean result;
        if (j == p.length()) {
            result = i == s.length();
        } else {
            boolean first = i < s.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.');
            if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
                result = match(i, j + 2) || (first && match(i + 1, j));
            } else {
                result = first && match(i + 1, j + 1);
            }
        }
        memo[i][j] = result;
        return result;
    }
}

Complexity

Time: O(m · n) — each state is solved once in O(1).
Space: O(m · n) — memo plus O(m + n) stack.

Bottom-Up 2-D Tabulation

TimeO(m · n).SpaceO(m · n).

Intuition

Fill dp[i][j] (suffix s[i..] vs suffix p[j..]) from the bottom-right corner. Note i must run all the way to m — an empty string can still match patterns like "a*b*".

Recurrence (with first = i < m && (p[j] == s[i] || p[j] == '.')):

dp[m][n] = true, dp[i][n] = false for i < m
if p[j+1] == '*': dp[i][j] = dp[i][j+2] || (first && dp[i+1][j])
else: dp[i][j] = first && dp[i+1][j+1]

Algorithm

dp = new boolean[m + 1][n + 1]; dp[m][n] = true.
For i = m down to 0, for j = n - 1 down to 0: apply the recurrence.
Return dp[0][0].

Dry Run

s = "aab", p = "c*a*b" (T = true). Columns at a '*' position (j = 1, 3) are never read and stay F:

i \ j	0 `c`	1 `*`	2 `a`	3 `*`	4 `b`	5 (end)
0 `a`	T	F	T	F	F	F
1 `a`	T	F	T	F	F	F
2 `b`	T	F	T	F	T	F
3 (end)	F	F	F	F	F	T

dp[2][4]: 'b' == 'b' and dp[3][5] = T. dp[1][2] (a* at 'a'): dp[1][4] = F but first && dp[2][2] = T. dp[0][0] (c*): skip it → dp[0][2] = T.

Code

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[m][n] = true; // empty string matches empty pattern
        for (int i = m; i >= 0; i--) {          // i == m: empty suffix of s
            for (int j = n - 1; j >= 0; j--) {
                boolean first = i < m && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.');
                if (j + 1 < n && p.charAt(j + 1) == '*') {
                    dp[i][j] = dp[i][j + 2] || (first && dp[i + 1][j]); // zero / one more
                } else {
                    dp[i][j] = first && dp[i + 1][j + 1];
                }
            }
        }
        return dp[0][0];
    }
}

Complexity

Time: O(m · n).
Space: O(m · n).

Space-Optimized 1-D DPOptimal

TimeO(m · n).SpaceO(n)

Intuition

Row i reads only row i (dp[i][j+2], already computed since j goes right-to-left) and row i + 1 (dp[i+1][j], dp[i+1][j+1]). Keep two 1-D arrays — next for row i + 1 and cur for row i — and swap after each row.

Algorithm

next = new boolean[n + 1] represents row m + 1 (all false, never matches).
For i = m down to 0:
- cur = new boolean[n + 1]; cur[n] = (i == m).
- For j = n - 1 down to 0: cur[j] = star ? cur[j+2] || (first && next[j]) : first && next[j+1].
- next = cur.
Return next[0].

Dry Run

flowchart TD
    A["row i=3 (empty s)<br/>[F,F,F,F,F,T]"] -->|"s[2]='b'"| B["row i=2<br/>[T,F,T,F,T,F]"]
    B -->|"s[1]='a'"| C["row i=1<br/>[T,F,T,F,F,F]"]
    C -->|"s[0]='a'"| D["row i=0<br/>[T,F,T,F,F,F]"]
    D --> E["cur[0] = true → match"]

Code

java

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[] next = new boolean[n + 1]; // row i+1 (starts as a dummy row past the end)
        for (int i = m; i >= 0; i--) {
            boolean[] cur = new boolean[n + 1];
            cur[n] = (i == m); // empty pattern only matches empty string
            for (int j = n - 1; j >= 0; j--) {
                boolean first = i < m && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.');
                if (j + 1 < n && p.charAt(j + 1) == '*') {
                    cur[j] = cur[j + 2] || (first && next[j]); // skip token / consume one char
                } else {
                    cur[j] = first && next[j + 1];
                }
            }
            next = cur; // current row becomes "row below" for i-1
        }
        return next[0];
    }
}

Complexity

Time: O(m · n).
Space: O(n) — two rows of the table.

Complexity Comparison

Approach	Time	Space
Recursion (Brute Force)	Exponential	O(m + n)
Top-Down Memoization	O(m · n)	O(m · n)
Bottom-Up 2-D Tabulation	O(m · n)	O(m · n)
Space-Optimized 1-D DP	O(m · n)	O(n)

Common Pitfalls

Treating '*' as a standalone wildcard (like glob *) — here it only repeats the preceding element; "a*" can match "".
Looking at p[j] == '*' instead of peeking at p[j + 1] — the decision about the star must be made at the token's first character.
Stopping the i loop at m - 1 — the empty-string row (i == m) is required for patterns like "a*" to match "" at the tail.
Returning true when i == m without checking the rest of the pattern — "a" vs "ab*c" must still fail because c remains.
Forgetting the first check in the star's "one more" branch — match(i + 1, j) alone would consume characters the token cannot match.