LeetCode #44 Hard

Wildcard Matching

Match an entire string against a pattern where ? matches one character and * matches any sequence.

stringdynamic-programminggreedy

02

Intuition

A star can absorb many different substring lengths, so blindly choosing its length can require extensive backtracking. The greedy insight is that only the most recent star needs reconsideration: ordinary characters and ? must match in place. Remember where that star occurred and how many string characters it currently covers. On a mismatch, expand its coverage by one and retry the pattern suffix.

How to spot this pattern

Wildcard matching differs from regex: stands alone and matches arbitrary characters. With only ? and , a linear greedy scan can use the latest star as a controlled backtracking checkpoint.

03

Approach

1

Advance through forced single-character matches

When pattern and string characters agree, or the pattern has ?, advance both pointers. These matches have no useful alternative to revisit unless an earlier star exists.

2

Record the latest star as a retry point

When the pattern pointer sees *, save its index and the current string index, then advance past the star. Initially the star represents an empty sequence.

3

Expand the saved star after a mismatch

If matching fails and a star was seen, increase the star's matched string endpoint by one, reset the string pointer there, and resume immediately after the star. Once the string ends, skip remaining stars and require the pattern to end.

04

Solution

▶1class Solution:
▶2    def isMatch(self, s: str, p: str) -> bool:
▶3        i = 0
▶4        j = 0
▶5        star = -1
▶6        matched = 0
▶7        while i < len(s):
▶8            if j < len(p) and (p[j] == s[i] or p[j] == '?'):
▶9                i += 1
▶10                j += 1
▶11            elif j < len(p) and p[j] == '*':
▶12                star = j
▶13                matched = i
▶14                j += 1
▶15            elif star != -1:
▶16                matched += 1
▶17                i = matched
▶18                j = star + 1
▶19            else:
▶20                return False
▶21        while j < len(p) and p[j] == '*':
▶22            j += 1
▶23        return j == len(p)

05

Common pitfalls

Giving wildcard star regex semantics

✗ Wrong

star repeats p[j - 1]

✓ Right

star matches any sequence of characters

In this problem * is an independent wildcard, not a postfix operator.

Retrying from the star itself

✗ Wrong

j = star

✓ Right

j = star + 1

The saved star already absorbs the expanded substring; matching must resume after it.

Rejecting leftover stars

✗ Wrong

return j == len(p)

✓ Right

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

A trailing star may match the empty sequence.

06

Edge cases

Empty string and all-star pattern

The final cleanup skips every star and accepts.

Consecutive stars

Each is recorded and skipped; their combined behavior is equivalent to one star.

No previous star at a mismatch

There is no flexible token to adjust, so return false immediately.

07

Complexity

Time

O(|s| + |p|)

Space

O(1)

Pointers advance linearly, with star expansion moving the saved string boundary forward.