44. Wildcard Matching

Problem¶

Determine whether pattern p matches all of string s, where:

? matches exactly one character.
* matches any number of characters, including zero.

s = "adceb", p = "*a*b" -> True

Key trick¶

Greedily match characters while remembering the most recent *. On a mismatch, let that * consume one more character and retry the pattern after it.

Trap¶

Naive backtracking repeatedly evaluates the same states and can take exponential time. Also, * may match zero characters, while ? must match exactly one.

Why is it interesting?¶

It looks like a dynamic programming problem, but controlled backtracking from only the latest * gives an \(O(n + m)\) greedy solution with constant extra space.

Python solution¶

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        i = j = 0
        match_idx = 0
        star_idx = -1

        while i < len(s):
            if j < len(p) and (p[j] == "?" or p[j] == s[i]):
                i += 1
                j += 1
            elif j < len(p) and p[j] == "*":
                # Remember where the latest star appeared and initially
                # let it match the empty string.
                match_idx = i
                star_idx = j
                j += 1
            elif star_idx != -1:
                # Let the latest star consume one more character.
                match_idx += 1
                i = match_idx
                j = star_idx + 1
            else:
                return False

        # Any remaining pattern characters must match the empty string.
        while j < len(p) and p[j] == "*":
            j += 1

        return j == len(p)

Time complexity: \(O(n + m)\).

Space complexity: \(O(1)\).

Comment on my solution¶

The recursive logic is mostly correct, but it explores the same (i, j) states many times, causing exponential runtime. The backtrack(i + 1, j + 1) branch for * is redundant because consuming with the star and then matching it as empty already covers that choice.

Memoization would reduce the runtime to \(O(nm)\) with \(O(nm)\) space, while the greedy solution avoids both the repeated states and recursion-depth risk.

# WRONG
# Time Limit Exceeded: 940/1812 testcases passed
# s = "aaabababaaabaababbbaaaabbbbbbabbbbabbbabbaabbababab"
# p = "*ab***ba**b*b*aaab*b"
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        # s = "aa", p = "a" -> False
        # s = "aa", p = "*" -> True
        # s = "cb", p = "?a" -> False

        def backtrack(i,j):
            if i == len(s):
                if j == len(p):
                    return True
                else:
                    # needed for p like this "****"
                    while j < len(p) and p[j] == "*":
                        j += 1
                    if j == len(p):
                        return True
                    else:
                        return False
            if j == len(p):
                return False

            pp = p[j]

            if pp == "*":
                if backtrack(i+1,j): # match one and continue matching any
                    return True
                if backtrack(i+1,j+1): # match one only
                    return True
                if backtrack(i,j+1): # match empty
                    return True
            if pp == "?" or pp == s[i]:
                return backtrack(i+1,j+1)

            return False

        return backtrack(0, 0)

Extra¶

About using match as variable name in above algorithm¶

Why using match variable name? It shadows the Python match. Even if we're not using it, it's ugly to do so.

match is a conventional name in this algorithm: it stores the string position reached by the most recent *. However, it is vague and visually conflicts with Python’s match soft keyword, even though using it as a variable is legal.

Can you elaborate?

There are two separate points: what the variable represents and what match means in Python.

What the variable represents¶

In the standard greedy wildcard algorithm, match stores the string boundary associated with the most recently encountered *.

Suppose execution reaches:

s = "adceb"
p = "*a*b"
     ^

When the first * is found:

Its pattern index is saved.
The current string index is saved in match.
The algorithm first assumes that * matches an empty string.

If a later mismatch occurs, the algorithm increments match, making that * consume one more character, and retries from immediately after the *.

Conceptually:

star_j = j
star_i = i

# First try: "*" consumes nothing.
j = star_j + 1

# After a later mismatch: "*" consumes one more character.
star_i += 1
i = star_i
j = star_j + 1

Therefore, match does not contain a match result. It contains a string index controlling how many characters the last * consumes. Names such as star_i, star_end, or star_consumed_until describe that role more precisely.

Is `match` actually shadowed?¶

Strictly speaking, no. Python’s match is:

Not a built-in function.
Not a regular reserved keyword.
A soft keyword recognized only in the syntax of a match statement.

Consequently, this is legal:

match = 3
print(match)

And Python can still use match as syntax in the appropriate context:

match value:
    case 3:
        print("three")

Unlike a reserved keyword such as class, return, or if, a soft keyword may still be used as an ordinary identifier where the grammar is unambiguous.

Why the name is still undesirable¶

Although there is no technical shadowing, match has two readability problems:

It visually resembles the match statement introduced in Python 3.10.
It sounds like a Boolean result or a matched object rather than a string index.

So the precise criticism is that match creates semantic and visual ambiguity, not that it shadows a built-in. In this implementation, star_i is the clearer name because it explicitly identifies the saved index in s associated with the latest *.