Wildcard Pattern Matching DP, in depth: the star recurrence, a worked table, linear-space DP, greedy and segment matchers with measured worst cases, and real glob semantics

From recursion to subproblems

Match from the left. If the pattern is empty, it matches only the empty string. If its first symbol is a literal or ?, it must consume the first character of the string, and the rest must match. If it is *, there are two choices: the star matches nothing, so drop it and match the rest of the pattern against the whole string; or the star absorbs one character, so keep the star and drop the first character of the string. That last choice is what lets a star swallow any number of characters one at a time.

def naive(s, p):
    if not p:
        return not s
    if p[0] == "*":
        return naive(s, p[1:]) or (bool(s) and naive(s[1:], p))
    return bool(s) and p[0] in ("?", s[0]) and naive(s[1:], p[1:])

This is correct and exponential. Every star doubles the branching, and the same suffix pairs are solved again and again. On s = aⁿ with a pattern of alternating stars and a ending in *b, so that it can never match, the function makes 762 calls at n = 8, 11,622 at n = 12 and 179,690 at n = 16, roughly fifteen times more for every four extra characters.

There are only (n + 1) times (m + 1) distinct subproblems, one per pair of suffixes, so memoising them, or filling a table, removes the blow-up. That observation is the whole of dynamic programming; see dynamic programming, cell by cell for the general method.

The recurrence and a worked table

Use prefixes instead of suffixes so the table fills top to bottom. Let D[i][j] be true when the first i characters of s match the first j symbols of p.

• D[0][0] is true: empty matches empty.
• D[0][j] is true only if p[:j] is all stars, so D[0][j] = D[0][j-1] and p[j-1] is a star.
• D[i][0] is false for i greater than 0: an empty pattern matches nothing else.
• If p[j-1] is a star: D[i][j] = D[i][j-1] (the star matches empty) or D[i-1][j] (the star absorbs s[i-1] and may absorb more).
• If p[j-1] is ? or equals s[i-1]: D[i][j] = D[i-1][j-1].
• Otherwise D[i][j] is false.

The star rule is the important difference from regex matching. Here the star is a symbol of its own, so absorbing a character never depends on the previous pattern symbol; in regex, x* can only absorb characters equal to x.

Read the table column by column. The first star column is true in every row, since a leading star matches any prefix. The a column is true only in the row for a, copied diagonally from the star column above. The second star column inherits that true value and carries it down through d, c and e. The final b column becomes true in the last row because s ends in b and the cell diagonally up-left is true. The string matches.

Linear-space implementation

Each row depends only on the row above and on cells to its left, so two rows of length m + 1 are enough. Collapsing runs of stars first does not change the answer and shrinks m.

def collapse(p: str) -> str:
    out = []
    for ch in p:
        if ch != "*" or not out or out[-1] != "*":
            out.append(ch)
    return "".join(out)

def wildcard_dp(s: str, p: str) -> bool:
    p = collapse(p)
    m = len(p)
    prev = [False] * (m + 1)
    prev[0] = True
    for j in range(1, m + 1):
        prev[j] = prev[j - 1] and p[j - 1] == "*"
    for ch in s:
        cur = [False] * (m + 1)          # cur[0] stays False
        for j in range(1, m + 1):
            if p[j - 1] == "*":
                cur[j] = cur[j - 1] or prev[j]
            elif p[j - 1] in ("?", ch):
                cur[j] = prev[j - 1]
        prev = cur
    return prev[m]

Time is O(nm) and space O(m). The cost is predictable: it depends only on the lengths, never on the content, which is the property you want when patterns come from users.

The greedy two-pointer matcher

The best-known alternative uses two pointers and remembers only the most recent star. Advance both pointers on a literal or ? match. On a star, record its position and the string position, and try matching it to nothing. On a mismatch, if a star has been seen, let it absorb one more character and retry from just after it; otherwise fail.

def wildcard_greedy(s: str, p: str) -> bool:
    i = j = 0
    star, mark = -1, 0
    while i < len(s):
        if j < len(p) and p[j] in ("?", s[i]):
            i += 1; j += 1
        elif j < len(p) and p[j] == "*":
            star, mark = j, i
            j += 1
        elif star != -1:
            j = star + 1
            mark += 1
            i = mark
        else:
            return False
    while j < len(p) and p[j] == "*":
        j += 1
    return j == len(p)

Why is it safe to forget earlier stars? Once a later star is reached, everything before it has been matched by some prefix of the string, and the later star can absorb whatever an earlier star would have taken extra. Moving an earlier star never creates a match the later star cannot. The algorithm is correct, and in a randomised comparison with the DP and the naive recursion over 30,000 small cases it disagreed zero times.

It is not linear, though. Its worst case is O(nm): on 1,000 a's against a star, 100 a's and a b, the loop ran 91,001 steps; at 4,000 a's and a 402-symbol pattern it ran 1,444,001. Each retry re-scans the segment after the star. On typical inputs it is far faster than the DP because it rarely retries, which is why it is popular, but treat its worst case as quadratic.

Segment search

Split the pattern on stars. The first segment must match at the start of the string, the last at the end, and every middle segment must appear in order in between. Taking the leftmost occurrence of each middle segment is always safe, because it leaves the most room for the segments after it.

def seg_at(s, i, seg):
    return all(c == "?" or c == s[i + k] for k, c in enumerate(seg))

def wildcard_segments(s: str, p: str) -> bool:
    if "*" not in p:
        return len(s) == len(p) and seg_at(s, 0, p)
    parts = p.split("*")
    head, tail = parts[0], parts[-1]
    if len(head) + len(tail) > len(s):
        return False
    if not (seg_at(s, 0, head) and seg_at(s, len(s) - len(tail), tail)):
        return False
    pos, end = len(head), len(s) - len(tail)
    for seg in parts[1:-1]:
        if not seg:
            continue
        k = next((i for i in range(pos, end - len(seg) + 1) if seg_at(s, i, seg)), -1)
        if k < 0:
            return False
        pos = k + len(seg)
    return True

This version agreed with the DP on the same 30,000 cases. With the naive inner search it is still O(nm) in the worst case. If segments contain no ?, replace the inner loop with a linear-time substring search such as KMP or Two-Way and the whole match runs in O(n + m), since each search resumes where the previous segment ended. Segments containing ? need a search that handles single-character wildcards; see string matching for the search algorithms.

Real glob semantics

Real glob implementations differ from the textbook problem in ways that cause bugs when ignored.

• Character classes. [abc], ranges such as [a-z] and negation such as [!a] each consume one character. In the DP they behave exactly like ? with a membership test, so tokenise the pattern first and keep the recurrence unchanged.
• Path separators. Python's fnmatch.fnmatchcase("a/b", "*") is true: fnmatch treats the slash as an ordinary character and matches leading dots. Shell and file-system globbing match one path component at a time, so * stops at a slash and hidden files need an explicit dot. Many tools add ** for crossing directories. Decide which semantics you need and test them.
• Case. Python's fnmatch.fnmatch normalises case using the operating system's rules, so it is case-insensitive on Windows; fnmatchcase never is. Pick one explicitly.
• Escaping. Decide how a literal star or question mark is written. In fnmatch, a bracket class such as [*] does it.

def class_end(p, i):
    """Index of the ] closing the class opened at p[i], or -1 if unclosed."""
    k = i + 1
    if p[k:k + 1] == "!":
        k += 1
    if p[k:k + 1] == "]":                # a leading ] is a literal member
        k += 1
    return p.find("]", k)

def tokenize(p):
    toks, i = [], 0
    while i < len(p):
        ch = p[i]
        if ch == "*":
            if not toks or toks[-1] != ("star",):
                toks.append(("star",))
            i += 1
        elif ch == "?":
            toks.append(("any",)); i += 1
        elif ch == "[" and class_end(p, i) != -1:
            j = class_end(p, i)
            body, neg = p[i + 1:j], False
            if body.startswith("!"):
                body, neg = body[1:], True
            chars, k = set(), 0
            while k < len(body):
                if k + 2 < len(body) and body[k + 1] == "-":
                    chars |= {chr(x) for x in range(ord(body[k]), ord(body[k + 2]) + 1)}
                    k += 3
                else:
                    chars.add(body[k]); k += 1
            toks.append(("cls", frozenset(chars), neg)); i = j + 1
        else:
            toks.append(("lit", ch)); i += 1
    return toks

Feed these tokens to the rolling DP, treating any, lit and cls as single-character tests. A version of this tokeniser checked against fnmatch.fnmatchcase on 30,000 random patterns with classes, ranges and negation agreed on every case. For path semantics, add a fourth test: a star cannot absorb a slash.

Operational guidance

Choose by threat model. If patterns come from untrusted users, the DP's fixed O(nm) cost is a guarantee; cap both lengths and the work is bounded. Translating a glob into a regex for a backtracking engine reintroduces the risk the DP removes; if you translate, target an automaton-based engine, as explained in regex engines. If patterns are trusted and inputs are short, the greedy matcher is the fastest simple choice.

Many patterns, one string. Routing tables and allowlists check one input against thousands of patterns. Index patterns by their literal head segment in a trie, so only patterns whose prefix matches are evaluated, and keep the patterns with a leading star in a separate list. Normalise before matching. Apply Unicode normalisation and case folding to both sides, or a visually identical string will slip past an allowlist.

Failure modes

• Prefix match instead of full match. Returning true when the pattern is used up but the string is not. Test aa against a: must be false.
• Trailing stars forgotten. abc against abc* must be true; the greedy loop needs its final star-skipping step.
• Empty string. The empty string matches *** and nothing containing a literal or ?.
• Exponential recursion. Unmemoised recursion or a backtracking regex on patterns with many stars.
• Semantics mismatch. A policy written assuming shell globs evaluated by a matcher where star crosses slashes grants more than intended.

Trade-offs

What to do next

1. Implement the rolling DP and the greedy matcher, and fuzz them against each other and a memoised recursion on short random strings.
2. Add the failure-mode cases above as fixed unit tests.
3. Write down your glob semantics: slashes, leading dots, case, classes and escaping.
4. Tokenise patterns once at load time and cap pattern and input lengths.
5. Measure the greedy matcher's worst case on your own longest inputs before choosing it.
6. Compare with the regex recurrence in regular expressions, in depth to see where the two problems diverge.