51. Wildcard Pattern Matching

Problem

Some rule systems, including alternative configurations of Fin's agent-authored routing rules and KB-title matching, use a simpler glob/wildcard pattern language instead of full regex: ? matches any single character, and * matches any sequence of characters, including the empty sequence. Unlike problem 27's regex *, which repeats the character immediately preceding it, this * is standalone — it stands for "any run of zero or more characters" on its own.

Given an incoming query string s and a wildcard pattern pattern, determine whether the pattern matches the ENTIRE query string, not just a substring of it.

Source: src/51_wildcard_pattern_matching.py

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

is_match("aa", "a")       # -> False   ("a" only matches one char, s has two)
is_match("aa", "*")       # -> True    ("*" matches any sequence, including "aa")
is_match("cb", "?a")      # -> False   ("?" matches "c", but "a" != "b")
is_match("adceb", "*a*b") # -> True
is_match("acdcb", "a*c?b") # -> False

Step-by-Step Approach

1. Let n = len(s), m = len(pattern). Build a (n+1) x (m+1) boolean DP table where dp[i][j] means "s[:i] (the first i characters of s) matches pattern[:j]" — i.e. matching prefixes, filled forward this time (unlike problem 27's backward-filled suffix table).
2. Base case: dp[0][0] = True, since two empty prefixes match.
3. Also handle the "leading stars" row: for j from 1 to m, if pattern[j-1] == "*", then dp[0][j] = dp[0][j-1] — a run of leading *s can still match an empty string prefix by each consuming zero characters.
4. Fill the table forward — i from 1 to n, j from 1 to m — so dp[i][j] can rely on already-computed cells above/to-the-left.
5. If pattern[j-1] is ? or matches s[i-1] exactly, this position lines up character-for-character, so dp[i][j] = dp[i-1][j-1] — the rest is exactly the previous subproblem, one character shorter on both sides.
6. If pattern[j-1] == "*", there are two ways to satisfy it: match zero characters of s at this position and move past the * in the pattern (dp[i][j-1]), or match one more character of s with this same * and stay on it (dp[i-1][j]). dp[i][j] is True if either option works: dp[i][j] = dp[i-1][j] or dp[i][j-1].
7. Otherwise (no match and not a *), dp[i][j] stays False (its default initialized value).
8. The answer is dp[n][m] — do the full strings match end to end?

The key insight is that a standalone * can absorb characters one at a time (dp[i-1][j], "consume one more of s, stay on this *") or be skipped entirely once it's done absorbing (dp[i][j-1], "move past this * in the pattern"), so the or of those two options captures every possible run length the * could cover without ever re-deriving it from scratch. Time and space are both O(n * m).

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
    n, m = len(s), len(pattern)
    # per-row list, avoids aliasing bug
    dp = [[False] * (m + 1) for _ in range(n + 1)]
    dp[0][0] = True
    # leading *s can still match an empty s prefix
    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):
            # exact char match or ? wildcard
            if pattern[j - 1] == "?" or pattern[j - 1] == s[i - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            elif pattern[j - 1] == "*":
                # skip * (0 chars) or consume one more char and stay on *
                dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
    return dp[n][m]

Key Functions & Tricks

• [[False] * (m + 1) for _ in range(n + 1)] — independent per-row list, sized (n+1) x (m+1), avoids the classic [[False] * (m+1)] * (n+1) row-aliasing bug.
• dp[i][j] — true when s[:i] matches pattern[:j], filled forward from prefixes (contrast with problem 27's backward suffix table).
• dp[0][j] = dp[0][j - 1] base-case loop — lets a run of leading *s match an empty string prefix.
• pattern[j - 1] == "?" or pattern[j - 1] == s[i - 1] — single-character wildcard or exact-match check, both fall through to the diagonal cell.
• *-handling — dp[i][j] = dp[i - 1][j] or dp[i][j - 1] combines "consume one more char of s" with "skip this * entirely" via or.

How to Recognize This Pattern