Generated by Codex with GPT-5

Quick facts

• Difficulty: HARD
• Problem: Wildcard Matching
• Main tags: String, Dynamic Programming, Greedy

What the problem is really asking

The pattern contains two special characters:

• ? matches exactly one character
• * matches any sequence of characters, including the empty sequence

The match must cover the entire string. That is the part that makes the problem interesting.

This is not a substring problem and it is not a “best effort” fuzzy match. Every character in the text and every character in the pattern has to be accounted for by one complete alignment.

The clean mental model

There are really only two kinds of pattern characters:

• rigid characters, which either match the current text character or they do not
• flexible *, which can decide to consume zero characters, one character, or many characters

If the pattern had no *, the solution would be trivial: walk both strings together and require exact matches except that ? can stand in for any single character.

So the whole challenge is how to handle * without trying every possible expansion.

The straightforward solution: dynamic programming

The most direct way to reason about the problem is to define a state:

dp[i][j] = whether text[:i] matches pattern[:j]

Then the transitions are simple:

• if pattern[j - 1] is a normal character, it matches only if it equals text[i - 1] and dp[i - 1][j - 1] was true
• if pattern[j - 1] is ?, it also depends on dp[i - 1][j - 1]
• if pattern[j - 1] is *, there are two important choices:
  • let it match nothing, which uses dp[i][j - 1]
  • let it absorb one more character, which uses dp[i - 1][j]

That gives a correct O(mn) solution for text length m and pattern length n.

It is a very good fallback in an interview because it is easy to justify. But this problem has a better final answer.

Why the greedy approach is enough

The key observation is that a mismatch only matters if there is no earlier * available to rescue it.

Suppose the algorithm has already matched everything up to some point and has seen a * at pattern index star_index.

At that moment, the algorithm can try the cheapest option first:

• treat the * as matching the empty string
• continue matching the rest of the pattern normally

If a mismatch happens later, the only useful recovery is to let that most recent * absorb one more text character and try again from the character after the star.

That works because:

• everything before that * has already been fixed and matched
• making the latest * slightly larger is the only way to repair the current mismatch without invalidating earlier work
• the amount matched by the * only moves forward, so no text position is retried infinitely

This gives the classic linear-time greedy algorithm with backtracking to the most recent star.

How to derive the greedy algorithm in an interview

A clean way to derive it is:

1. Start from the DP idea so the matching rules are completely clear.
2. Notice that * is the only source of branching.
3. Ask what information is actually needed from the past when a mismatch happens.

The answer is surprisingly small:

• where the most recent * was in the pattern
• where in the text that * started matching

That is enough because when a mismatch happens later, the algorithm can retry exactly one alternative: make that * cover one more character.

So the greedy state becomes:

• text_index
• pattern_index
• last_star_index
• matched_after_star_index

Once that state is written down, the implementation becomes short and mechanical.

Best approach

The best practical solution for this problem is the greedy two-pointer algorithm with star backtracking.

It runs in O(m + n) time in practice for this matching model and uses O(1) extra space.

The DP solution is still worth understanding because it explains the matching rules clearly and is easier to generalize to more complicated wildcard systems. But for this exact LeetCode problem, the greedy version is the one interviewers usually hope to see after the DP discussion.

Python solution

The implementation below uses a small normalization helper to collapse repeated * characters into one. That is not required for correctness, but it makes the matching state easier to reason about and avoids redundant work.

class WildcardMatcher:
    """Match a text string against a wildcard pattern with ? and *."""

    @staticmethod
    def normalize_pattern(pattern: str) -> str:
        """
        Collapse consecutive stars because '**' behaves exactly like '*'.
        This keeps the greedy state compact and avoids pointless retries.
        """
        normalized_characters: list[str] = []
        previous_was_star = False

        for character in pattern:
            if character == "*":
                if previous_was_star:
                    continue
                previous_was_star = True
            else:
                previous_was_star = False

            normalized_characters.append(character)

        return "".join(normalized_characters)

    def matches(self, text: str, pattern: str) -> bool:
        """Return True if the entire text matches the entire pattern."""
        normalized_pattern = self.normalize_pattern(pattern)

        text_index = 0
        pattern_index = 0

        # Track the most recent star and the first text index it tried to cover.
        last_star_index = -1
        matched_after_star_index = 0

        while text_index < len(text):
            current_pattern_matches = (
                pattern_index < len(normalized_pattern)
                and (
                    normalized_pattern[pattern_index] == "?"
                    or normalized_pattern[pattern_index] == text[text_index]
                )
            )

            if current_pattern_matches:
                text_index += 1
                pattern_index += 1
                continue

            if (
                pattern_index < len(normalized_pattern)
                and normalized_pattern[pattern_index] == "*"
            ):
                # First, try to let the star match an empty sequence.
                last_star_index = pattern_index
                matched_after_star_index = text_index
                pattern_index += 1
                continue

            if last_star_index != -1:
                # A previous star can absorb one more character and we retry
                # from the token immediately after that star.
                matched_after_star_index += 1
                text_index = matched_after_star_index
                pattern_index = last_star_index + 1
                continue

            return False

        # Any remaining pattern characters must all be stars.
        while (
            pattern_index < len(normalized_pattern)
            and normalized_pattern[pattern_index] == "*"
        ):
            pattern_index += 1

        return pattern_index == len(normalized_pattern)


class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        matcher = WildcardMatcher()
        return matcher.matches(s, p)

Interview follow-ups

What if the interviewer asks for the dynamic programming solution first?

That is a very reasonable request, and it is often the cleanest way to start. The DP state is dp[i][j], meaning whether the first i characters of the string match the first j characters of the pattern. A normal character or ? depends on dp[i - 1][j - 1], while * depends on either dp[i][j - 1] for matching nothing or dp[i - 1][j] for matching one more character. This solution is easy to prove correct because it explicitly enumerates the legal ways each pattern character can behave. The tradeoff is cost: it uses O(mn) time and usually O(mn) space unless the table is compressed to one dimension.

What changes if * is limited to matching at most k characters?

The greedy solution stops being enough, because the whole trick depended on being able to keep extending the most recent star without worrying about a cap. Once each star has a maximum length, the algorithm must remember how much of that budget has already been used. That pushes the problem back toward dynamic programming or memoized search, where the state includes the string index, the pattern index, and how much of the current star’s allowance has been consumed. The complexity increases because the matcher now has to reason about many bounded choices rather than one unbounded flexible token.

How would you return one valid expansion of each *, not just whether a match exists?

For that version, the easiest approach is usually to use DP or memoization and store parent pointers so the algorithm can reconstruct one successful path after it finds a match. Each time a * transition is chosen, the reconstruction can record whether that star matched zero characters or extended over one more character. The greedy matcher can still help conceptually, but it is much less convenient for reconstruction because it is designed to answer existence quickly, not to preserve the full sequence of choices. The main tradeoff is extra memory: reconstruction requires storing enough history to replay the decisions after the boolean result is known.

What if the wildcard language also includes character classes like [abc] or ranges like [a-z]?

The same high-level structure still applies, but the matching rule for a single pattern token becomes richer. A normal token is no longer just one literal character or ?; it may represent a set of allowed characters. If the language remains regular and the tokens still behave locally, dynamic programming adapts naturally because each state transition only needs a predicate that answers whether the current token can consume the current text character. The greedy star-based shortcut may or may not remain valid depending on the exact grammar, so in a more feature-rich matcher, DP is usually the safer answer even if it is less space-efficient.

Practical takeaway

The hard part of this problem is not the syntax of ? and *. The hard part is realizing that only the most recent * needs to stay “live” as a backtracking option.

Once that clicks, the solution becomes:

• match rigid characters directly
• record the most recent *
• on mismatch, extend that * by one character and retry

That turns an exponential-looking search space into a compact greedy scan.