LeetCode #10 Hard

Regular Expression Matching

Decide whether an entire string matches a pattern containing . and *.

stringdynamic-programmingrecursion

02

Intuition

Greedily consuming as many characters as possible for can prevent the remainder from matching. At each string and pattern position, the future depends only on those two indices, making it a two-dimensional dynamic-programming state. A following creates two choices: skip the repeated token or consume one matching character and keep the pattern position. Memoization explores both without repeating the same suffix work.

How to spot this pattern

Whole-string matching with operators that can consume variable amounts usually requires DP over string and pattern positions. A postfix star naturally creates skip-versus-consume transitions.

03

Approach

1

Describe matching by two suffix indices

Let match(i, j) mean that s[i:] matches p[j:] completely. If the pattern is exhausted, success requires the string to be exhausted too.

2

Compute whether the current tokens agree

The first characters match only when i is in range and either the pattern character equals s[i] or is .. This guard prevents reading beyond the string.

3

Branch only when the pattern token has a star

If p[j + 1] is *, either skip the token-star pair with match(i, j + 2) or consume one matching character with match(i + 1, j). Without a star, both indices must advance together.

04

Solution

▶1class Solution:
▶2    def isMatch(self, s: str, p: str) -> bool:
▶3        @cache
▶4        def match(i, j):
▶5            if j == len(p):
▶6                return i == len(s)
▶7            first = i < len(s) and (p[j] == s[i] or p[j] == '.')
▶8            if j + 1 < len(p) and p[j + 1] == '*':
▶9                return match(i, j + 2) or (first and match(i + 1, j))
▶10            return first and match(i + 1, j + 1)
▶11 
▶12        return match(0, 0)

05

Common pitfalls

Treating star as an independent character

✗ Wrong

first = p[j] == '*'

✓ Right

if j + 1 < len(p) and p[j + 1] == '*':

Star modifies the preceding token rather than matching input itself.

Advancing past star after consuming once

✗ Wrong

match(i + 1, j + 2)

✓ Right

match(i + 1, j)

The same starred token may consume additional characters.

Accepting when only the string ends

✗ Wrong

if i == len(s):
    return True

✓ Right

if j == len(p):
    return i == len(s)

Remaining pattern literals may still make the match invalid.

06

Edge cases

Empty string with pattern a*

The zero-occurrence branch skips the pair and reaches two exhausted suffixes.

Pattern .*

The dot matches any current character and the star may repeatedly consume it.

A trailing unmatched literal

The base case rejects the match because the pattern is not exhausted with the string.

07

Complexity

Time

O(|s| * |p|)

Space

O(|s| * |p|)

Each pair of suffix indices is evaluated once.