44. Wildcard Pattern Matching

Problem

An internal launch tool lets researchers select which checkpoints to include in an eval sweep using a glob-style filter: ? matches any single character, and * matches any sequence of characters, including the empty sequence. Given a run name and a filter pattern, determine whether the pattern matches the ENTIRE run name, not just a substring of it.

This is the classic LC44 wildcard-matching problem — distinct from full regular- expression matching in that * here is a standalone token meaning "any sequence," not tied to the character preceding it.

Source: src/44_wildcard_pattern_matching.py

def is_match(s: str, pattern: str) -> bool: ...

>>> is_match("run-042", "run-*")
True

>>> is_match("run-042", "run-4*")
False

Step-by-Step Approach

1. Define dp[i][j] as "does s[:i] match pattern[:j]," so the answer is dp[n][m] for the full strings.
2. Base case: dp[0][0] = True (empty matches empty). Then handle a leading run of * in the pattern against an empty s: dp[0][j] is True only if every pattern character up to j is *, since * can absorb zero characters.
3. Fill the table row by row (increasing i). For each cell, look at pattern[j-1]: if it's ? or matches s[i-1] exactly, the cell inherits dp[i-1][j-1] (both sides consume one character).
4. If pattern[j-1] is *, it can either match zero characters (dp[i][j-1]) or absorb one more character of s while staying on the same pattern position (dp[i-1][j]) — the cell is True if either option is.
5. Any other mismatch leaves the cell False (its default).
6. Return dp[n][m].

The key insight is that * creates a branch, not a single transition: it can be treated as "used up" (drop it and keep the current s position) or "still active" (keep it and consume one more s character) — the DP cell just needs to be true under either interpretation.

Reference solution

def is_match(s: str, pattern: str) -> bool:
    # dp[i][j] = whether s[:i] matches pattern[:j], filled forward,
    # O(len(s) * len(pattern)) time/space -- classic LC44 grid DP
    n, m = len(s), len(pattern)
    dp = [[False] * (m + 1) for _ in range(n + 1)]
    dp[0][0] = True
    # a leading run of '*' can still match the empty string
    for j in range(1, m + 1):
        if pattern[j - 1] == "*":
            dp[0][j] = dp[0][j - 1]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if pattern[j - 1] == "?" or pattern[j - 1] == s[i - 1]:
                dp[i][j] = dp[i - 1][j - 1]  # consume one char on both sides
            elif pattern[j - 1] == "*":
                # '*' matches zero chars (dp[i][j-1]) or one more char (dp[i-1][j])
                dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
    return dp[n][m]

Key Functions & Tricks

• dp[i][j] grid — rows are prefixes of s, columns are prefixes of pattern; classic 2D matching-DP layout.
• Leading-* row initialization — without it, a pattern like "**" would incorrectly fail to match an empty s.
• dp[i - 1][j] or dp[i][j - 1] — encodes the two ways a * can behave (absorb one more char, or stop absorbing).
• 1-indexed DP table with a +1-sized grid — lets index 0 cleanly represent "empty prefix" without special-casing negative indices.
• Iterative bottom-up fill instead of memoized recursion — avoids Python recursion- depth limits on long strings.

How to Recognize This Pattern