Regular Expression Matching — Solution

Problem

Given a string and a pattern, determine if the pattern fully matches the string. The pattern supports two special characters: '.' which matches any single character, and '*' which matches zero or more of the character immediately before it.

• Input: s = "aab", p = "cab"
• Output: true
• Explanation: c* matches zero 'c's, a* matches two 'a's, and b matches 'b'.

Counter-example: s = "mississippi", p = "misisp*." returns false — the final '.' needs to match one character but the pattern runs out of string in the right way, and 'p*' can't bridge the mismatch between "issipi" and "isp.".

Intuition

The '*' wildcard makes this impossible to solve left-to-right greedily, because you never know whether consuming zero or more characters is the right choice until you see what comes later. Dynamic programming resolves this by asking a simpler question at each cell: does s[0..i-1] match p[0..j-1]? The answer depends only on already-computed neighbors, so the table fills in bottom-up without re-exploring any subproblem.

Approach 1 — Recursion

At each step, look one character ahead in the pattern: if the next character is '', branch into two choices — skip the "x" pair entirely (zero occurrences) or consume one string character if it matches the preceding pattern character. Otherwise, simply check whether the current characters match and recurse on the rest.

1. If the pattern is empty, return whether the string is also empty.
2. Check if the first characters match (string non-empty, and p[0] is '.' or equals s[0]).
3. If p[1] is '*', either skip the pair (isMatch(s, p[2:])) or, when the first characters match, consume one from the string (isMatch(s[1:], p)).
4. Otherwise, require the first characters to match, then recurse on the tails.

1def isMatch(s: str, p: str) -> bool:
2    if not p:
3        return not s
4
5    # Does the pattern's first character match the string's first character?
6    first_matches = bool(s) and (p[0] == s[0] or p[0] == '.')
7
8    if len(p) >= 2 and p[1] == '*':
9        # Either use '*' as zero occurrences of the preceding char,
10        # or consume one matching char and keep the same pattern.
11        return isMatch(s, p[2:]) or (first_matches and isMatch(s[1:], p))
12    else:
13        return first_matches and isMatch(s[1:], p[1:])

Time: O(2^(m+n)) — each '*' doubles the branching factor and calls repeat on overlapping suffixes.

Space: O(m+n) — the maximum recursion depth when the pattern has no '*'.

Approach 2 — Bottom-Up Dynamic Programming

Build a 2D table where dp[i][j] is true if s[0..i-1] matches p[0..j-1]. Fill the table row by row; each cell needs only the cell above it and two cells to its left, so the answer for any prefix pair is available when needed.

1. Allocate a (m+1) × (n+1) boolean table, initialized to false.
2. Set dp[0][0] = true: empty string matches empty pattern.
3. Seed the first row: for each j where p[j-1] == '', dp[0][j] = dp[0][j-2], because "x" can match an empty string.
4. Fill each cell: if p[j-1] == '*', set dp[i][j] = dp[i][j-2] (zero occurrences) OR, when p[j-2] matches s[i-1], set dp[i][j] |= dp[i-1][j] (one more occurrence).
5. Otherwise, if p[j-1] is '.' or equals s[i-1], set dp[i][j] = dp[i-1][j-1].
6. Return dp[m][n].

1def isMatch(s: str, p: str) -> bool:
2    m, n = len(s), len(p)
3    # dp[i][j] = True if s[:i] fully matches p[:j]
4    dp = [[False] * (n + 1) for _ in range(m + 1)]
5    dp[0][0] = True
6
7    # Empty string can match patterns like "a*", "a*b*", etc.
8    for j in range(2, n + 1):
9        if p[j - 1] == '*':
10            dp[0][j] = dp[0][j - 2]  # "x*" eliminates preceding char from pattern
11
12    for i in range(1, m + 1):
13        for j in range(1, n + 1):
14            if p[j - 1] == '*':
15                # Zero occurrences: pretend the "x*" pair isn't there
16                dp[i][j] = dp[i][j - 2]
17                # One more occurrence: preceding pattern char must match current string char
18                if p[j - 2] == s[i - 1] or p[j - 2] == '.':
19                    dp[i][j] = dp[i][j] or dp[i - 1][j]
20            elif p[j - 1] == '.' or p[j - 1] == s[i - 1]:
21                dp[i][j] = dp[i - 1][j - 1]
22
23    return dp[m][n]

Time: O(m·n) — each of the (m+1)×(n+1) cells is computed in O(1).

Space: O(m·n) — the full DP table; reducible to O(n) with a rolling array since each row only depends on the previous.

Complexity Summary

Common Mistakes

• Seeding the first row incorrectly — dp[0][j] must be initialized before filling the rest of the table, otherwise patterns like "ca" will never match the empty string even though they should.
• Indexing into the pattern for '*' at j=1 — when p[j-1] == '', the preceding character is p[j-2]. If j < 2, the '' would be the first character, which is invalid input per the problem constraints; forgetting this can cause an index-out-of-bounds in 0-indexed languages.
• Confusing '*' with wildcard-matching semantics — here '' only repeats the immediately preceding character, not any arbitrary sequence. Writing dp[i][j] = dp[i-1][j-1] for a '' cell is wrong.
• Forgetting the zero-occurrences branch — when p[j-1] == '', the first thing to check is whether dropping the "x" pair (dp[i][j-2]) makes it match; skipping this means the algorithm can never eliminate optional pattern elements.
• Using the same index twice in the recursion — in the recursive version, passing isMatch(s[1:], p[1:]) when p[1]=='' is incorrect; the pattern should stay the same (isMatch(s[1:], p)) so the '' can match multiple characters.

Related Problems

• wildcard-matching — the same matching frame but '*' means any sequence of characters rather than repetitions of one, requiring a different DP transition
• edit-distance — 2D DP over two strings where each cell depends on up, left, and diagonal neighbors
• longest-common-subsequence — core 2D DP pattern on two strings; understanding this makes the regex DP structure click
• interleaving-string — another 2D DP where you track how far through two sequences you've consumed