Regular Expression Matching
Regular Expression Matching: decide whether an entire string matches a pattern containing . and *.
- 1 <= s.length <= 20
- 1 <= p.length <= 20
- s contains only lowercase English letters.
- p contains only lowercase English letters, '.', and '*'.
- It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.
Intuition
Regular expression matching decides whether an entire string matches a pattern containing . (any single character) and * (zero or more of the preceding element). The * is what makes this Hard — it has no fixed length, so you cannot align the two strings position by position.
Greedy consumption fails, and the reason is worth seeing. Matching "aaa" against "a*a", if a* greedily eats all three characters, nothing is left for the trailing a and the match fails — even though taking only two would have worked. The right number of repetitions depends on what comes after, which greedy cannot see.
So both possibilities must be explored. The saving grace is that the outcome depends only on the two current positions — where you are in the string and where you are in the pattern:
- match(i, j) asks whether s[i:] matches p[j:], and its answer depends on nothing but i and j.
That makes it a two-dimensional DP with n × m states, and memoisation turns the exponential branching into a table.
The branching itself is small. When the next pattern token is followed by *, there are exactly two moves: skip the token entirely by advancing the pattern two positions, or consume one matching character by advancing the string while leaving the pattern where it is. Without a *, both indices advance together on a match and the branch fails otherwise.
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.
Approach
Before reading on: price up what the direct approach costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(|s| * |p|) time and O(|s| * |p|) space.
Define the state as two suffix indices
match(i, j) means s[i:] matches p[j:] completely. The future depends only on these two positions, which is what makes memoisation valid and reduces the search to n × m distinct states.
Handle the exhausted pattern
If j reaches the end of the pattern, the match succeeds only when i has also reached the end of the string. Leftover characters with no pattern remaining is a failure, not a partial match.
Test whether the current characters agree
The first characters match when i is in range and either p[j] equals s[i] or p[j] is .. Checking i is in range first is essential — the pattern may still have tokens when the string has run out.
Branch two ways on a star
If p[j+1] is *, try skipping the token with match(i, j+2), or consuming one character with match(i+1, j) when the current characters agree. Either succeeding is enough; greedy would commit to one and lose valid matches.
Advance both indices without a star
With no * following, the tokens must match one-to-one: advance both i and j. If the characters disagree, this branch fails immediately with no alternative to try.
Memoise on the index pair
Cache results keyed by (i, j). Without caching the same suffix pair is recomputed exponentially often — with it, each of the n × m states is solved once.
Cost of the memoised search
There are n × m states each doing O(1) work, giving O(n·m) time and the same space for the cache. The bottom-up table version has identical bounds and avoids recursion depth on long inputs.
Solution & live demo
Common pitfalls
Treating star as an independent character
first = p[j] == '*'
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
match(i + 1, j + 2)
match(i + 1, j)
The same starred token may consume additional characters.
Accepting when only the string ends
if i == len(s):
return Trueif j == len(p):
return i == len(s)Remaining pattern literals may still make the match invalid.
Edge cases
a*The zero-occurrence branch skips the pair and reaches two exhausted suffixes.
.*The dot matches any current character and the star may repeatedly consume it.
The base case rejects the match because the pattern is not exhausted with the string.