Wildcard String Matching: Recursive and DP Solutions

Wildcard string matching decides whether text t matches pattern p, where ? replaces any single character and * replaces any sequence including the empty one.

The twist that makes this harder than substring search: * is not a positional match. It can expand to cover zero characters or a hundred. Scanning left to right character-by-character fails the moment you hit a *. You need to try every possible expansion, and that is where dynamic programming saves both time and your interview.

This article covers the recursive approach with memoisation, the full bottom-up DP solution, a step-by-step trace of the 6x5 dp table for pattern g*ks matching text geeks, and a complexity comparison of all three approaches.

The Two Wildcards Defined

The problem uses exactly two special characters:

Character	Matches
?	Any single character, exactly one
*	Any sequence of characters, zero or more

Everything else in the pattern is a literal and must match the corresponding character in the text exactly.

Three test cases to calibrate behaviour:

Pattern	Text	Result	Reason
Am?zo	Amazon	False	? covers exactly one char; pattern expects 5 characters, text has 6
Am?z*on	Amazkfdsaon	True	? matches a, * absorbs kfdsa
g*ks	geeks	True	* absorbs ee between g and ks

Two edge cases worth fixing before writing a single line of code. First: * matches the empty string, so g*ks matches gks directly. Second: if the text is empty but the pattern is g*, the match fails because g still needs at least one character to match, regardless of what * does after it. Only a pattern made entirely of * characters can match an empty text.

The original FACE Prep article on this topic included a third character +, defined as one-or-more occurrences of the previous character. That variant appears in some company-specific tests. The two-character set (? and *) is the standard version, matching LeetCode 44 and the pattern used in most product company interviews.

Recursive Solution with Memoisation

The recursive logic follows three rules applied at each position (i, j), where i indexes into the text and j indexes into the pattern:

• If pattern[j] is *: try two branches. Skip the star (advance j, keep i) or use the star to consume one text character (keep j, advance i).
• If pattern[j] is ? or equals text[i]: both characters match, advance both pointers.
• Otherwise: return false.

The base case is: if both pointers reach the end simultaneously, return true. If only the pattern pointer runs out, return false.

Without memoisation, every * in the pattern doubles the branching factor, giving O(2^(m+n)) worst-case time. A memoisation table of size (m+1) x (n+1) stores each (i, j) result after its first computation so no sub-problem is solved twice.

C++ with memoisation:

#include <bits/stdc++.h>
using namespace std;

bool helper(const string& t, const string& p, int i, int j,
            vector<vector<int>>& memo) {
    // Both exhausted: full match
    if (i == (int)t.size() && j == (int)p.size()) return true;
    // Pattern exhausted but text is not: no match
    if (j == (int)p.size()) return false;
    // Cached result
    if (memo[i][j] != -1) return memo[i][j];

    if (p[j] == '*') {
        bool skip = helper(t, p, i, j + 1, memo);           // star matches empty
        bool use  = (i < (int)t.size()) &&
                    helper(t, p, i + 1, j, memo);            // star absorbs t[i]
        return memo[i][j] = skip || use;
    }
    if (i < (int)t.size() && (p[j] == '?' || p[j] == t[i]))
        return memo[i][j] = helper(t, p, i + 1, j + 1, memo);
    return memo[i][j] = false;
}

bool wildcardMatch(const string& text, const string& pattern) {
    int m = text.size(), n = pattern.size();
    vector<vector<int>> memo(m + 1, vector<int>(n + 1, -1));
    return helper(text, pattern, 0, 0, memo);
}

Python with lru_cache:

from functools import lru_cache

def wildcard_match(text: str, pattern: str) -> bool:
    @lru_cache(maxsize=None)
    def dp(i: int, j: int) -> bool:
        if i == len(text) and j == len(pattern):
            return True
        if j == len(pattern):
            return False
        if pattern[j] == '*':
            # Skip star (match empty) or consume one text character
            return dp(i, j + 1) or (i < len(text) and dp(i + 1, j))
        if i < len(text) and (pattern[j] == '?' or pattern[j] == text[i]):
            return dp(i + 1, j + 1)
        return False
    return dp(0, 0)

The Python version uses a closure over text and pattern, so the cache key is just (i, j), with no need to pass the strings into each call.

When do you pick memoised recursion over bottom-up DP? In an interview, the recursive version is often easier to explain because it mirrors the problem statement directly. The bottom-up table is faster in practice (no call stack overhead) and preferred for production code.

Companies like MAQ Software include string and DP problems of this class in their written tests. Walking the interviewer through the three-rule logic before writing code typically earns more credit than jumping straight to a table.

Bottom-Up DP Solution

Define dp[i][j] as true if text[0..i-1] matches pattern[0..j-1]. The table has (m+1) rows and (n+1) columns, with row 0 and column 0 representing empty prefixes.

Base cases:

• dp[0][0] = true: empty text matches empty pattern.
• dp[i][0] = false for all i > 0: no pattern means no match for non-empty text.
• First row (empty text, non-empty pattern): dp[0][j] = dp[0][j-1] if pattern[j-1] == '*', else false. A run of leading stars can cover empty text; any literal breaks the chain.

Transitions for i >= 1 and j >= 1:

• If pattern[j-1] == '*': dp[i][j] = dp[i-1][j] OR dp[i][j-1].
  • dp[i-1][j] covers the case where the star consumes text[i-1].
  • dp[i][j-1] covers the case where the star matches empty and we skip past it.
• If pattern[j-1] == '?' or pattern[j-1] == text[i-1]: dp[i][j] = dp[i-1][j-1].
• Otherwise: dp[i][j] = false.

C++:

bool wildcardMatchDP(const string& text, const string& pattern) {
    int m = text.size(), n = pattern.size();
    // dp[i][j] = text[0..i-1] matches pattern[0..j-1]
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
    dp[0][0] = true;

    // Base row: empty text matches only all-star patterns
    for (int j = 1; j <= n; ++j)
        dp[0][j] = dp[0][j - 1] && (pattern[j - 1] == '*');

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (pattern[j - 1] == '*')
                dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
            else if (pattern[j - 1] == '?' || pattern[j - 1] == text[i - 1])
                dp[i][j] = dp[i - 1][j - 1];
        }
    }
    return dp[m][n];
}

Python:

def wildcard_match_dp(text: str, pattern: str) -> bool:
    m, n = len(text), len(pattern)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True

    # Base row: leading stars can cover empty text
    for j in range(1, n + 1):
        dp[0][j] = dp[0][j - 1] and pattern[j - 1] == '*'

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if pattern[j - 1] == '*':
                dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
            elif pattern[j - 1] == '?' or pattern[j - 1] == text[i - 1]:
                dp[i][j] = dp[i - 1][j - 1]

    return dp[m][n]

The GeeksforGeeks wildcard matching article and LeetCode 44 both use this table structure and are the standard reference and practice problem for this topic.

Worked Trace: ‘g*ks’ Matching ‘geeks’

Pattern g*ks has 4 characters: g (j=1), * (j=2), k (j=3), s (j=4). Text geeks has 5 characters: g (i=1), e (i=2), e (i=3), k (i=4), s (i=5).

The dp table is 6 rows by 5 columns. T = true, F = false:

	""	g	*	k	s
""	T	F	F	F	F
g	F	T	T	F	F
e	F	F	T	F	F
e	F	F	T	F	F
k	F	F	T	T	F
s	F	F	T	F	T

Row-by-row fill explanation:

• Base row (i=0): dp[0][0]=T. Pattern g at j=1 is a literal, so dp[0][1]=F. For j=2 with pattern *: dp[0][2] = dp[0][1] AND (pattern[1]=='*') = F AND T = F. The run breaks because g before * already failed. All remaining base cells stay F.
• Row g (i=1): dp[1][1]: pattern g matches text g, so dp[0][0] = T. dp[1][2]: pattern * uses dp[0][2] OR dp[1][1] = F OR T = T. Cells for k and s are F (pattern k vs text g, pattern s vs text g, both mismatches).
• Rows e (i=2 and i=3): dp[i][1]: pattern g vs text e, mismatch, so F. dp[i][2]: pattern * uses dp[i-1][2] OR dp[i][1] = T OR F = T. The * column stays true because dp[i-1][2] carries forward from the previous row as the star absorbs each e. Cells for k and s stay F.
• Row k (i=4): dp[4][2]: pattern * uses dp[3][2] OR dp[4][1] = T OR F = T. dp[4][3]: pattern k vs text k, match, so dp[3][2] = T. dp[4][4]: pattern s vs text k, mismatch, so F.
• Row s (i=5): dp[5][2]: pattern * uses dp[4][2] OR dp[5][1] = T OR F = T. dp[5][3]: pattern k vs text s, mismatch, so F. dp[5][4]: pattern s vs text s, match, so dp[4][3] = T.

dp[5][4] = T, so geeks matches g*ks.

The * column at j=2 acts as a propagator: once it turns on at row g (because pattern g matched the first character), it carries true downward via the dp[i-1][j] clause in the star transition. The literal k at j=3 and s at j=4 then confirm the tail of the match.

Complexity Analysis

Approach	Time	Space
Naive recursion (no memo)	O(2^(m+n)) worst case	O(m+n) call stack
Memoised recursion	O(m x n)	O(m x n)
Bottom-up DP	O(m x n)	O(m x n)
Bottom-up DP, rolling row	O(m x n)	O(n)

The rolling-row optimisation replaces the full table with two alternating rows: prev and curr. The star transition (dp[i][j] = dp[i-1][j] OR dp[i][j-1]) needs prev[j] and curr[j-1], both available in the two-row version. The ? or literal transition (dp[i][j] = dp[i-1][j-1]) needs prev[j-1], which requires saving one value before overwriting. In a placement interview, the bottom-up DP with O(m x n) space is the standard answer; mention the rolling-row variant only if the interviewer asks about space optimisation specifically.

For reference across other classic DP and data structure problems from this cluster, the data structures programs guide covers arrays, linked lists, stacks, queues, and sorting in C++, Java, and Python.

The same DP table logic that resolved g*ks against geeks in 30 cells runs at scale inside sequence alignment tools and tokeniser matching routines. If you want to move from tracing DP cells on paper to building tools that actually run inference, TinkerLLM gives you that environment at ₹299, a working sandbox where the projects deploy to GitHub rather than staying in a notes file.