Wildcard Pattern Matching: Optimization and Implementation

1. Introduction and Core Concepts

Wildcard pattern matching is a fundamental string matching problem where a pattern containing special wildcard characters must be matched against an input text. Unlike exact string matching, wildcard pattern matching introduces flexibility by allowing certain symbols to represent variable character sequences. The two most common wildcards are ?, which matches exactly one arbitrary character, and *, which matches any sequence of characters including the empty sequence. This simple yet powerful abstraction forms the backbone of file globbing, search filters, and URL routing.

At its core, wildcard pattern matching answers a boolean question: does the entire input string match the entire pattern? This is distinct from substring search, where the pattern may appear anywhere inside the text. For example, the pattern a*b?c matches axxxbzc because * can expand to xxx and ? matches z, but it does not match aab because the final characters do not align. The requirement for full-string coverage makes the problem more constrained and algorithmically interesting than simple containment checks.

Why does wildcard pattern matching matter? From an algorithmic perspective, it is a canonical example of dynamic programming, illustrating optimal substructure and overlapping subproblems in a highly intuitive way. From a systems perspective, it is ubiquitous. Operating systems use it to resolve file paths like *.log or data_??.csv, databases use it to implement LIKE queries, and web frameworks use it for route matching. Understanding its theory and optimization is essential for building efficient, scalable software that handles user-defined search patterns without catastrophic performance degradation.

Core Definitions and Wildcard Semantics

The problem is typically formalized as: given a text string s of length m and a pattern string p of length n, determine if p matches s completely. The alphabet consists of regular characters plus the two wildcards. The ? wildcard is straightforward — it consumes exactly one character from s. The * wildcard is more complex because it introduces non-determinism: it can consume zero, one, or many characters, and the optimal choice depends on the remainder of the pattern.

This non-determinism is what makes brute-force recursion exponential. A naive approach that tries every possible expansion for each * will explore a combinatorial number of paths. Dynamic programming tames this complexity by memoizing whether a prefix of the string matches a prefix of the pattern, turning an exponential search into a polynomial-time table-filling exercise. The classic DP formulation also naturally handles edge cases such as consecutive * characters, which are functionally equivalent to a single *, and patterns that start or end with wildcards.

Wildcard vs. Regular Expression Matching

It is important to distinguish wildcard pattern matching from regular expression matching, although they are often confused. Regular expressions support a far richer set of operators including ., * (with different semantics), +, character classes, and alternation. In regex, * means zero or more repetitions of the preceding element, whereas in wildcard matching, * stands alone and means zero or more of any character. Wildcard matching is strictly less expressive than full regex, which is an advantage: its limited operator set allows for more efficient, linear-time greedy algorithms that are impossible for general regex engines.

2. How It Works

The mechanism behind wildcard pattern matching can be understood through the lens of state transitions. Imagine scanning both the string and pattern from left to right. When both characters are normal letters and they are equal, we advance both pointers. When the pattern has a ?, we advance both pointers regardless of the string character. The difficulty arises when we encounter *: we must decide how many characters it should consume before the next pattern character is attempted.

Dynamic programming models this decision as a recurrence relation. Let dp[i][j] be true if the first i characters of s match the first j characters of p. The recurrence has three cases. If p[j-1] is a normal character or ?, then dp[i][j] = dp[i-1][j-1] provided the characters match. If p[j-1] is *, then dp[i][j] = dp[i][j-1] or dp[i-1][j]. The first term corresponds to using * to match an empty sequence, the second to using it to consume one more character from s and staying on the same pattern character.

The base cases are critical. dp[0][0] = True because two empty strings match. dp[0][j] is true only if the first j characters of the pattern consist entirely of *, since only * can match an empty string. All other entries in the first row and column are false. Filling the table row by row yields the answer at dp[m][n]. This bottom-up approach guarantees that every subproblem is solved before it is needed.

The Greedy Two-Pointer Insight

While DP is intuitive and guarantees correctness, it is not the most efficient solution. A key observation is that wildcard pattern matching with only ? and * has a greedy property. When we encounter a *, we can tentatively assume it matches zero characters and remember its position. If a later mismatch occurs, we backtrack and let that last * consume one more character. This backtracking never needs to reconsider earlier * characters beyond the most recent one, which allows a linear-time, constant-space algorithm.

This greedy algorithm maintains four pointers: s_idx and p_idx for current positions, plus star_idx and s_tmp_idx to remember the last * and the string position it has matched up to. The algorithm advances when characters match, records star positions when * is seen, and backtracks when a mismatch occurs but a previous star exists. If no star is available to backtrack to, the match fails. This elegant mechanism eliminates the need for a DP table entirely.

3. Implementation

Implementing wildcard pattern matching correctly requires careful handling of indices, edge cases, and pattern preprocessing. Below are four canonical Python implementations, each illustrating a different trade-off between clarity, time, and space. All implementations assume ? matches one character and * matches any sequence.

Bottom-Up Dynamic Programming (2D Table)

This is the most educational implementation and directly mirrors the recurrence relation. It is easy to debug and extend, making it ideal for interviews when clarity is prioritized over optimal space.

def is_match_dp(s: str, p: str) -> bool:
    """
    Bottom-up DP for wildcard pattern matching.
    dp[i][j] = True if s[:i] matches p[:j]
    Time: O(m*n), Space: O(m*n)
    """
    m, n = len(s), len(p)
    # dp dimensions (m+1) x (n+1)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True

    # Pattern prefix of only '*' can match empty string
    for j in range(1, n + 1):
        if p[j - 1] == '*':
            dp[0][j] = dp[0][j - 1]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                # '*' matches empty (dp[i][j-1]) or one more char (dp[i-1][j])
                dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
            elif p[j - 1] == '?' or s[i - 1] == p[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            # else remains False
    return dp[m][n]

# Example
print(is_match_dp("adceb", "*a*b"))  # True
print(is_match_dp("acdcb", "a*c?b")) # False

Top-Down Memoization (Recursive DP)

Top-down memoization is often more intuitive to derive during an interview because it starts from the natural recursive definition. It also benefits from pruning: it only explores states that are actually reachable.

from functools import lru_cache

def is_match_memo(s: str, p: str) -> bool:
    """
    Top-down DP with memoization.
    Recurrence: match(i,j) depends on match(i+1,j+1), match(i+1,j), match(i,j+1)
    """
    m, n = len(s), len(p)

    @lru_cache(maxsize=None)
    def dfs(i: int, j: int) -> bool:
        # If pattern exhausted, string must also be exhausted
        if j == n:
            return i == m
        # If string exhausted, remaining pattern must be all '*'
        if i == m:
            return all(p[k] == '*' for k in range(j, n))

        if p[j] == '*':
            # Two choices: '*' matches empty (j+1) or matches s[i] (i+1)
            return dfs(i, j + 1) or dfs(i + 1, j)
        elif p[j] == '?' or s[i] == p[j]:
            return dfs(i + 1, j + 1)
        else:
            return False

    return dfs(0, 0)

# Preprocess to collapse consecutive '*' for efficiency
def collapse_stars(p: str) -> str:
    res = []
    for ch in p:
        if ch == '*' and res and res[-1] == '*':
            continue
        res.append(ch)
    return ''.join(res)

Space-Optimized DP (1D Array)

The 2D DP only needs the previous row to compute the current row, so space can be reduced from O(m*n) to O(n). This is a common optimization follow-up in interviews.

def is_match_optimized(s: str, p: str) -> bool:
    """
    Space-optimized DP using 1D array.
    Time: O(m*n), Space: O(n)
    """
    m, n = len(s), len(p)
    prev = [False] * (n + 1)
    curr = [False] * (n + 1)
    prev[0] = True

    for j in range(1, n + 1):
        if p[j - 1] == '*':
            prev[j] = prev[j - 1]

    for i in range(1, m + 1):
        curr[0] = False  # non-empty s cannot match empty p
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                # curr[j-1] is dp[i][j-1], prev[j] is dp[i-1][j]
                curr[j] = curr[j - 1] or prev[j]
            elif p[j - 1] == '?' or s[i - 1] == p[j - 1]:
                curr[j] = prev[j - 1]
            else:
                curr[j] = False
        prev, curr = curr, prev  # swap rows

    return prev[n]

Greedy Two-Pointer (Optimal Linear Solution)

This is the production-grade solution. It runs in O(m+n) average time with O(1) extra space and is what you would use in a real system handling millions of patterns.

def is_match_greedy(s: str, p: str) -> bool:
    """
    Greedy two-pointer with backtracking.
    Time: O(m*n) worst, O(m+n) average, Space: O(1)
    """
    m, n = len(s), len(p)
    s_idx = 0
    p_idx = 0
    star_idx = -1
    s_tmp_idx = -1

    while s_idx < m:
        # Direct match or '?' wildcard
        if p_idx < n and (p[p_idx] == '?' or p[p_idx] == s[s_idx]):
            s_idx += 1
            p_idx += 1
        # '*' found, track its position and the string position
        elif p_idx < n and p[p_idx] == '*':
            star_idx = p_idx
            s_tmp_idx = s_idx
            p_idx += 1
        # Mismatch but previous '*' exists, backtrack
        elif star_idx != -1:
            p_idx = star_idx + 1
            s_tmp_idx += 1
            s_idx = s_tmp_idx
        else:
            return False

    # Check remaining pattern chars are all '*'
    while p_idx < n and p[p_idx] == '*':
        p_idx += 1

    return p_idx == n

# Test
print(is_match_greedy("mississippi", "m*iss*iss*"))  # True
print(is_match_greedy("abefcdgiescdfimde", "ab*cd*ef*")) # False

4. Step-by-Step Example

To solidify the DP recurrence, let us walk through a concrete example in detail. Consider string s = "adceb" (m=5) and pattern p = "*a*b" (n=4). The pattern means: any prefix, then a, then any sequence, then b. We expect the result to be True because "adceb" starts with a and ends with b with "dce" in between.

We construct a DP table with rows 0..5 for s and columns 0..4 for p. Initialization: dp[0][0]=True. For the first row (empty string), dp[0][1]=True because p[0]='*' can match empty, dp[0][2]=False because "*a" cannot match empty, and similarly dp[0][3]=False, dp[0][4]=False. The first column (empty pattern) is all False except dp[0][0].

Now we fill row by row. For i=1 (s[0]='a'): j=1 (p[0]='*') gives dp[1][1] = dp[1][0] or dp[0][1] = False or True = True — the * consumes 'a'. j=2 (p[1]='a') gives dp[1][2] = dp[0][1] = True because 'a'=='a'. j=3 (p[2]='*') gives dp[1][3] = dp[1][2] or dp[0][3] = True or False = True. j=4 (p[3]='b') gives dp[1][4]=False because 'a' != 'b'. This row shows that prefix "a" matches "*", "*a", and "*a*" but not "*a*b".

Continuing the Fill

For i=2 (s[1]='d'): j=1 ('*') stays True via dp[1][1], j=2 ('a') becomes False because 'd' != 'a', j=3 ('*') becomes True via dp[2][2] or dp[1][3] = False or True = True, and j=4 remains False. The pattern "*a*" still matches because the second * can absorb 'd'.

Skipping to the final row i=5 (s[4]='b'): we have dp[5][1]=True, dp[5][2]=False, dp[5][3]=True (since "*a*" matches any string containing a), and crucially dp[5][4] = dp[4][3] = True because p[3]='b' matches s[4]='b' and the prefix "adce" matched "*a*". Thus dp[5][4]=True, confirming a full match. This trace reveals how * propagates True values across rows and columns, effectively allowing flexible consumption.

Greedy Walkthrough for the Same Example

With the greedy algorithm, we start with s_idx=0, p_idx=0, star_idx=-1. p[0]='*' so we set star_idx=0, s_tmp_idx=0, p_idx=1. Now p[1]='a' matches s[0]='a', so both advance. p[2]='*' sets star_idx=2, s_tmp_idx=1, p_idx=3. p[3]='b' does not match s[1]='d', so we backtrack: p_idx=3, s_tmp_idx=2, s_idx=2. Still mismatch with s[2]='c', backtrack again to s_idx=3, then s_idx=4 where s[4]='b' matches p[3]='b'. Both advance to end, remaining pattern is empty, so we return True. The greedy approach needed only 3 backtracks instead of filling 20 DP cells.

5. Complexity Analysis

Complexity analysis for wildcard pattern matching depends heavily on the chosen implementation strategy. The naive recursive solution without memoization has exponential time complexity O(2^(m+n)) in the worst case because each * branches into two recursive calls. This is unacceptable for any non-trivial input and serves only as a baseline to motivate optimization.

The classic 2D DP solution improves this to O(m*n) time and O(m*n) space, where m is the length of the string and n is the length of the pattern. This holds for best, average, and worst cases because the table must be fully populated regardless of early mismatches. The space-optimized 1D DP retains O(m*n) time but reduces space to O(n), or O(min(m,n)) if we transpose to ensure the shorter dimension is used for the array. This is often the expected answer in interviews when asked to optimize space.

The greedy two-pointer algorithm offers the best practical performance. Its worst-case time is still O(m*n), which occurs with patterns like "*a*a*a*a*" and strings like "aaaaaaaa" that force repeated backtracking. However, its average case is O(m+n) and its best case is O(min(m,n)) when the pattern fails early or contains no stars. Its space complexity is O(1), making it ideal for embedded systems or high-throughput servers.

Pattern preprocessing, such as collapsing consecutive * into a single *, costs O(n) time and can significantly reduce the effective n. For example, "a*****b***c" becomes "a*b*c", shrinking n from 11 to 5 and reducing DP work by more than half. This preprocessing is almost always worthwhile and should be mentioned as a free optimization.

When analyzing best-case scenarios, consider early termination. If the pattern starts with a literal that does not match the string's first character and contains no leading *, both DP and greedy can fail in O(1) or O(n) time. However, DP still allocates the full table, while greedy exits immediately, highlighting why greedy is superior for negative matches in production filters.

6. Variations and Optimizations

Beyond the standard ? and * wildcards, several variations and optimizations are relevant for real systems. One common extension is supporting an escape character, typically \, to allow literal matching of ? and *. Another is adding character classes like [abc] or [0-9], which moves the problem closer to globbing as implemented in Unix shells. Each extension modifies the recurrence but retains the DP structure.

A powerful optimization is pattern preprocessing. Collapsing consecutive stars is the simplest, but more advanced preprocessing includes removing redundant patterns such as "*?*" which can be simplified, or analyzing the pattern to determine if it can be split into literal segments separated by *. For patterns with many literals, you can use efficient substring search like KMP or Boyer-Moore to locate the literal segments first, then verify wildcard gaps. This hybrid approach can be sublinear in practice.

For scenarios where many strings are matched against the same pattern, compiling the pattern into a deterministic finite automaton (DFA) or nondeterministic finite automaton (NFA) can amortize costs. The wildcard pattern can be converted to an NFA with epsilon transitions for *, then simulated in O(m) per string after O(n) compilation. This is analogous to regex compilation and is used in databases that repeatedly apply the same LIKE pattern to millions of rows.

Advanced Techniques

Bit-parallelism is another optimization for short patterns. By encoding the DP row as bitsets, you can process 64 characters in parallel using bitwise operations, achieving O((m*n)/w) time where w is the word size. This technique, borrowed from Myers' algorithm for approximate string matching, is effective when m and n are under a few hundred characters and is used in bioinformatics for wildcard matching in DNA sequences.

When matching must be done on streaming data or very large files that do not fit in memory, a streaming greedy algorithm with bounded backtracking is preferred. It processes the input character by character without storing the entire string, maintaining only the star positions and a small buffer. If the input is too large for O(m*n) DP, this streaming approach guarantees O(1) memory at the cost of potential re-scanning.

7. Real-World Applications

Wildcard pattern matching is not an abstract academic exercise; it is embedded in nearly every layer of modern computing. In operating systems, file globbing is the most visible application. When a user types rm *.tmp or ls report_202?.pdf in a shell, the shell expands the wildcard pattern to matching file names using exactly the algorithm described. The efficiency of this expansion directly impacts user experience when directories contain millions of files.

Web servers and frameworks rely heavily on wildcard routing. Frameworks like Express.js, Django, and Spring use patterns such as /api/users/*/profile or /static/** to route incoming HTTP requests to handlers. A request path must be matched against dozens or hundreds of route patterns per request, often at rates of thousands of requests per second. A linear-time greedy matcher is essential here; a quadratic DP would become a bottleneck and a potential denial-of-service vector if attackers send crafted URLs with many wildcards.

Databases implement wildcard matching for the SQL LIKE and ILIKE operators. A query like SELECT * FROM customers WHERE name LIKE 'Sm%th' requires scanning rows and applying wildcard matching. Database engines often optimize this by using indexes for prefix patterns like 'Sm%' but fall back to full wildcard matching for patterns with leading % (the SQL equivalent of *). Understanding the complexity helps database designers decide when to use full-text search indexes instead of naive LIKE scans.

Networking and Security Uses

In networking, firewall rules and access control lists use wildcard patterns to match IP addresses, hostnames, and URLs. For example, a rule might block *.malicious.com or allow 192.168.1.*. Network packet filters must evaluate these patterns at line rate, often in hardware or highly optimized C code, where the O(1) space greedy algorithm is mandatory.

Security tools use wildcard matching for log analysis and intrusion detection. Searching logs for patterns like "Failed login for * from IP *" helps detect brute-force attacks. Antivirus engines use wildcard signatures to detect malware variants where certain bytes are allowed to vary. In all these cases, the pattern is often user-provided, so robust handling of edge cases and prevention of algorithmic complexity attacks (e.g., patterns that cause worst-case O(m*n) backtracking) is critical.

8. Comparison with Alternatives

Choosing the right string matching technique depends on the problem's requirements. Wildcard pattern matching occupies a sweet spot between exact matching and full regular expressions, offering more flexibility than the former and better performance than the latter. Understanding its trade-offs helps architects select the appropriate tool.

Exact string matching algorithms like Knuth-Morris-Pratt (KMP), Boyer-Moore, and Rabin-Karp are optimized for finding a literal substring without wildcards. They achieve O(m+n) or even sublinear time but cannot handle variable-length gaps. Regular expressions can handle wildcards and much more, but their generality comes at the cost of higher complexity, potential exponential backtracking, and larger engine overhead. Wildcard matching is simpler to implement correctly and to reason about for security.

Glob matching, as used in shells, is essentially wildcard matching with additional features like ** for recursive directory traversal and {a,b} for alternation. Standard wildcard matching is the core subset of glob. For simple filtering tasks, wildcard matching is often sufficient and faster than invoking a full glob or regex engine.

For interview and system design contexts, the key takeaway is: if the problem statement mentions only ? and * and requires full-string matching, use the wildcard DP or greedy solution. If it mentions . and * where * means repetition of the previous character, it is LeetCode 10 (Regular Expression Matching) and requires a different DP. If it requires finding a substring, KMP is more appropriate. Misidentifying the problem type is a common source of incorrect solutions.

9. Common Mistakes and Best Practices

Even experienced engineers make subtle errors when implementing wildcard pattern matching. The most frequent mistake is mishandling the empty string cases. Many implementations incorrectly return False when both string and pattern are empty, or fail to handle patterns like "*" or "***" matching an empty string. The base case dp[0][0]=True and the initialization loop for dp[0][j] must be explicitly tested.

Another common pitfall is off-by-one errors in DP indexing. Since dp[i][j] corresponds to s[i-1] and p[j-1], it is easy to accidentally compare s[i] with p[j] or to iterate with incorrect bounds. Using helper variables m and n and clearly commenting the meaning of each DP cell prevents this. Similarly, in the greedy algorithm, forgetting to handle trailing * after the main loop causes patterns like "a*" to incorrectly fail on string "a".

A third mistake is not collapsing consecutive *. While functionally correct to leave them, they cause unnecessary DP states and extra backtracking steps. In worst-case inputs crafted to exploit this, performance can degrade significantly. A simple preprocessing pass that replaces "**" with "*" in a loop should be standard practice.

Best Practices for Robust Implementation

Always preprocess the pattern. Beyond collapsing stars, consider trimming whitespace if patterns come from user input and normalizing case if matching should be case-insensitive. For case-insensitive matching, convert both strings to the same case before matching rather than adding case checks inside the hot loop.

Choose the right algorithm for the context. For interviews, start with the 2D DP for clarity, then offer the 1D optimization and greedy solution as follow-ups. For production code, default to the greedy two-pointer unless you need to extend to more complex wildcards, in which case DP is more maintainable. Document the time and space guarantees in comments so future maintainers understand the trade-offs.

Test comprehensively. Essential test cases include: empty string and empty pattern, pattern with only *, pattern with only ?, string longer than pattern, pattern longer than string, consecutive *, * at start/middle/end, and large random stress tests comparing DP and greedy results for consistency. Also test for potential ReDoS: patterns like "*a*a*a*a*a*b" against strings of many as should complete quickly with the greedy algorithm but may be slow with naive recursion.

• Validate inputs: ensure pattern contains only allowed characters or handle invalid wildcards gracefully.
• Use iterative DP over recursion to avoid stack overflow for long strings (m, n up to 10^4).
• Prefer O(1) greedy for high-throughput services; reserve O(m*n) DP for offline or extended wildcard features.
• Benchmark with realistic data sizes; theoretical O(m*n) may be fine for m,n < 100 but not for m,n > 5000.
• Consider early exits: if pattern has no * and lengths differ, immediate mismatch when accounting for ?.

10. Interview Questions

Wildcard pattern matching is a staple of coding interviews, appearing in various forms at top technology companies. Interviewers use it to assess dynamic programming fundamentals, optimization intuition, and attention to edge cases. Below are common questions and how to approach them effectively.

Question 1: Implement Wildcard Matching (LeetCode 44)

Prompt: Given an input string s and a pattern p, implement wildcard pattern matching with support for ? and *. ? matches any single character. * matches any sequence (including empty). The matching should cover the entire input string.

Approach: Start by clarifying semantics: full match vs substring, and whether * can be escaped. Propose the DP solution first, explain the recurrence dp[i][j] = dp[i][j-1] or dp[i-1][j] for *, and code the 2D table. Then discuss optimization to 1D and the greedy O(1) space solution. Mention collapsing stars as preprocessing. This progression shows depth beyond just coding the basic solution.

Question 2: Optimize Space to O(n)

Prompt: Can you solve the same problem using only O(n) extra space where n is pattern length?

Approach: Explain that dp[i][j] only depends on dp[i-1][j-1], dp[i][j-1], and dp[i-1][j], so only two rows are needed. Show the 1D array implementation where prev[j] holds the previous row and curr[j] is computed left to right, with careful handling of curr[j-1] for the * case. Discuss that you can further optimize to O(min(m,n)) by ensuring the array corresponds to the shorter dimension.

Question 3: Count Distinct Matches or Return All Matches

Prompt: Instead of boolean, count how many ways the pattern can match the string, or return the matched substrings for each *.

Approach: Change the DP from boolean to integer counting: dp[i][j] += dp[i][j-1] + dp[i-1][j] for *, with appropriate base cases. For returning substrings, augment DP to store back-pointers or use recursion with path reconstruction. This tests whether you truly understand the DP structure versus memorizing the boolean version.

Question 4: Wildcard Matching vs Regular Expression Matching

Prompt: What is the difference between wildcard matching (?, *) and regex matching (., *)? Can you solve both?

Approach: Clearly articulate the semantic difference: wildcard * stands alone, regex * repeats the preceding element. Show the regex DP recurrence: if p[j-1]=='*' then dp[i][j] = dp[i][j-2] or (dp[i-1][j] if s[i-1]==p[j-2] or p[j-2]=='.'). Emphasize that regex requires looking back two characters, while wildcard does not. This demonstrates precise understanding and prevents confusion.

Question 5: Design a File System Glob Filter

Prompt: Design a system that filters millions of file names against thousands of wildcard patterns efficiently.

Approach: This is a system design extension. Propose preprocessing patterns (collapse stars, extract literal prefixes/suffixes), building a trie or Aho-Corasick automaton for literal segments, and using the greedy matcher for verification. Discuss indexing strategies, caching compiled patterns, and using bit-parallel matching for short patterns. Mention handling of ** for recursive directory matching and the need to avoid ReDoS by limiting pattern complexity. This shows ability to scale the core algorithm to production.