Wildcard Matching — String DP with `?` and `*` Done Cleanly

Problem Statement#

Given an input string s and a pattern p, implement wildcard pattern matching with support for two metacharacters:

• ? matches any single character.
• * matches any sequence of characters, including the empty sequence.

The match must cover the entire input string — partial matches do not count. Return true if p matches s, otherwise false.

Example: s = "aa", p = "a" returns false. "a" does not match the entire string.

Example: s = "aa", p = "*" returns true. * matches any sequence including "aa".

Example: s = "cb", p = "?a" returns false. The ? matches c, but a does not match b.

Example: s = "adceb", p = "*a*b" returns true. The first * matches the empty string, a matches a, the second * matches dce, and b matches b.

Constraints: 0 is less than or equal to s.length, p.length is less than or equal to 2000. The pattern can be much shorter than the string.

Why This Problem Matters#

Wildcard Matching is the canonical 2D DP question for string algorithms at Meta, Amazon, Google, and most large-cap tech companies. It tests your ability to design a clean recurrence under three subtle conditions: a literal character match, a ? single-character wildcard, and a * variable-length wildcard.

Compared to its sibling Regular Expression Matching (LeetCode 10), Wildcard is simpler because * does not depend on the preceding character — it stands alone and matches anything. That subtle difference changes the recurrence and the base case row.

The problem is also a great stage to demonstrate two things interviewers explicitly grade: the difference between memoization and tabulation, and a clever O(1)-memory two-pointer technique that runs in linear time on most inputs.

The Core Insight (Recurrence)#

Define dp[i][j] as true iff the first i characters of s match the first j characters of p. Recurrence cases:

• p[j-1] == s[i-1] or p[j-1] == '?': characters align. dp[i][j] = dp[i-1][j-1].
• p[j-1] == '*': two sub-cases combined with OR.
  • Treat * as matching the empty sequence: dp[i][j] = dp[i][j-1].
  • Treat * as consuming one more character of s: dp[i][j] = dp[i-1][j].
  • Combined: dp[i][j] = dp[i][j-1] OR dp[i-1][j].
• Otherwise: dp[i][j] = false.

Base cases:

• dp[0][0] = true (empty string matches empty pattern).
• dp[0][j] = dp[0][j-1] if p[j-1] == '*', otherwise false. A pattern matches the empty string only if every prefix character is *.

The first row is the trap. Many candidates initialize it to false and miss patterns like "***a" matching the empty string up through index 3. Spend an extra ten seconds explaining this aloud.

Building the DP Solution (Recursion to Memo to Tabulation)#

Top-down: match(i, j) returns whether s[0..i) matches p[0..j). Recurse on the three cases. Memoize on (i, j) to get O(m * n) time and O(m * n) memory plus stack.

Tabulation: allocate dp[m + 1][n + 1] with dp[0][0] = true. Fill the first row using the all-* rule. Then iterate row by row.

Space optimization: each dp[i][j] reads dp[i-1][j-1], dp[i-1][j], and dp[i][j-1]. Keep two rolling rows of length n + 1 and reduce memory to O(n).

Two-pointer optimization: walk both strings with greedy backtracking on the most recent *. Achieves O(m * n) worst case and O(m + n) in practice with O(1) extra memory. Many interviewers love seeing this as a follow-up.

Visual Dry Run (DP Table Trace)#

Trace s = "abcd", p = "*c?d". The table has 5 rows (i = 0..4) and 5 columns (j = 0..4).

Row i = 0 (empty s):

• dp[0][0] = true. dp[0][1] (*) = dp[0][0] = true. dp[0][2] (c) = false. dp[0][3] (?) = false. dp[0][4] (d) = false.

Row i = 1 (s[0] = a):

• dp[1][1] (*) = dp[1][0] OR dp[0][1] = false OR true = true.
• dp[1][2] (c): a != c, false.
• dp[1][3] (?): match, dp[0][2] = false.
• dp[1][4] (d): a != d, false.

Row i = 2 (s[1] = b):

• dp[2][1] (*) = dp[2][0] OR dp[1][1] = false OR true = true.
• dp[2][2] (c): b != c, false.
• dp[2][3] (?): match, dp[1][2] = false.
• dp[2][4] (d): false.

Row i = 3 (s[2] = c):

• dp[3][1] (*) = true.
• dp[3][2] (c): match, dp[2][1] = true.
• dp[3][3] (?): match, dp[2][2] = false.
• dp[3][4] (d): c != d, false.

Row i = 4 (s[3] = d):

• dp[4][1] (*) = true.
• dp[4][2] (c): d != c, false.
• dp[4][3] (?): match, dp[3][2] = true.
• dp[4][4] (d): match, dp[3][3] = false. Wait — dp[3][3] was false, so dp[4][4] would be false. Let me recheck: dp[3][3] (? matches c) needs dp[2][2] which is b vs c, false. So dp[4][4] would seem false.

But intuitively *c?d should match abcd: * consumes a, c matches c, ? matches anything (could be b?). Actually ? matches a single character, so the alignment is * -> "ab", c -> "c", but then ?d has to match "d" which is one character — ? would need to match nothing. That fails. The correct alignment is * -> "a", c -> ?, etc. — let me redo: * -> "", c would need to match a, fails. * -> "a", c -> b fails. * -> "ab", c -> c works, then ? -> d... but then d has nothing to match. So actually s = abcd does NOT match *c?d because there is no character left for the trailing d after ? consumes one.

So dp[4][4] = false is correct. To get a true answer try s = "abcdd" against *c?d: * -> ab, c -> c, ? -> d, d -> d, true.

This dry run highlights why the table fill matters — every cell depends on three predecessors.

Optimized Solution — Space-Optimized Python and JavaScript#

Python — Two-Pointer Greedy#

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        i, j = 0, 0
        star = -1
        match = 0
        m, n = len(s), len(p)
        while i < m:
            if j < n and (p[j] == '?' or p[j] == s[i]):
                i += 1
                j += 1
            elif j < n and p[j] == '*':
                star = j
                match = i
                j += 1
            elif star != -1:
                j = star + 1
                match += 1
                i = match
            else:
                return False
        while j < n and p[j] == '*':
            j += 1
        return j == n

JavaScript — Two-Pointer Greedy#

var isMatch = function (s, p) {
  let i = 0;
  let j = 0;
  let star = -1;
  let match = 0;
  const m = s.length;
  const n = p.length;
  while (i < m) {
    if (j < n && (p[j] === '?' || p[j] === s[i])) {
      i += 1;
      j += 1;
    } else if (j < n && p[j] === '*') {
      star = j;
      match = i;
      j += 1;
    } else if (star !== -1) {
      j = star + 1;
      match += 1;
      i = match;
    } else {
      return false;
    }
  }
  while (j < n && p[j] === '*') j += 1;
  return j === n;
};

Complexity Analysis#

• DP tabulation: time O(m * n), space O(m * n) or O(n) with rolling rows.
• Memoization: same asymptotics as tabulation plus stack overhead.
• Two-pointer greedy: O(m * n) worst case but O(m + n) in practice with O(1) extra memory.
• Pattern preprocessing (collapse consecutive stars to one) often gives a 2x speedup since ** is equivalent to *.

Common Mistakes#

• Initializing the first row to all false. Patterns like "*", "**", or "*" followed by literals require the all-star prefix rule.
• Forgetting that * matches the empty sequence. Many candidates encode only the consumption case (dp[i][j] = dp[i-1][j]) and miss the empty-match branch.
• Confusing with regex. In LeetCode 10 (Regular Expression Matching), * means "zero or more of the preceding character." Wildcard is simpler — * stands alone.
• Failing to handle empty pattern with non-empty string. Always returns false. The base case row catches this.
• Forgetting the trailing-stars consumption in the two-pointer version. After the main loop, you must skip remaining stars in p.

Interview Tips#

• Lead with the DP recurrence, walk through both * cases, and explicitly state the first-row base case rule. That earns immediate credit.
• Code the tabulation first because it is the cleanest version. Mention the rolling-row optimization as an aside.
• If the interviewer asks for O(1) memory, pivot to the two-pointer greedy. Walk through the backtrack-to-last-star intuition with a short example.
• Discuss preprocessing: collapse consecutive * runs to a single *. It does not change the language matched but speeds up real inputs.

Follow-up Questions#

• Implement Regular Expression Matching (LeetCode 10) — same shape, but * couples to the preceding character.
• Edit Distance / Levenshtein. Same 2D table, transitions are insert / delete / replace.
• Find the actual matched alignment, not just true or false. Reconstruct from the DP table.
• Generalize to Unicode strings or case-insensitive matching. Constants change but the recurrence holds.

Key Takeaways#

• Wildcard Matching is a classic 2D string DP with three branches: literal match, ? single-character wildcard, and * variable-length wildcard.
• The first-row base case is the common trap — patterns of all *s must match the empty string.
• DP tabulation runs in O(m * n) time and O(n) space with rolling rows; memoization is a top-down equivalent.
• The two-pointer greedy backtracks on the most recent * and runs in O(m + n) practical time with O(1) memory — the senior-level upgrade.
• Wildcard differs from Regex Matching because * is independent of the previous character, simplifying the recurrence.
• Mastering this template extends naturally to Edit Distance, Distinct Subsequences, and Shortest Common Supersequence.