44. Wildcard Matching

Given a string s and a pattern p containing ? (matches any single char) and * (matches any sequence, including the empty one), decide if p matches all of s. A 2D DP table over prefixes of both strings resolves every wildcard cleanly in O(m·n).

● Hard2D DPString MatchingTypeScript

PROBLEM What we're solving

Return true if string s is fully matched by pattern p. Rules: ? matches any single character; * matches any sequence of characters, including the empty sequence. The match must cover the entire string, not just a substring.

Concrete example: s="adceb", p="*a*b" → true. The first * matches the empty sequence, a matches a, the second * matches dce, and b matches the final b.

Another: s="cb", p="?a" → false (? matches c, but a ≠ b). s="aa", p="*" → true.

KEY IDEA Build truth about prefixes bottom-up

Insight → Define dp[i][j] as "does s[0..i-1] match p[0..j-1]?". When the pattern char is *, it forks into exactly two choices: match the empty sequence — drop the * and keep the same s prefix (dp[i][j-1]) — OR absorb one more character of s and let the * keep going (dp[i-1][j]). Either path succeeding makes dp[i][j] true.

RECIPE Filling the DP table

0 · Base case. dp[0][0] = true (empty matches empty). For the top row (i = 0): a leading run of * can match the empty string, so dp[0][j] = dp[0][j-1] whenever p[j-1] === '*' (and false the moment a non-* char appears).
1 · Pattern char is *.Two ways to succeed, OR'd together:
Empty match: the * contributes nothing → dp[i][j-1].
Absorb a char: the * eats s[i-1] and stays available → dp[i-1][j].
2 · Pattern char is ? or an exact match. Consume one char from each side → dp[i][j] = dp[i-1][j-1].
3 · Otherwise. A literal char that doesn't equal s[i-1] — mismatch, leave dp[i][j] = false.

Classic confusion → Here * is standalone — it matches any sequence by itself. That is NOT the same * as in Regex Matching (LC 10), where * binds to the precedingcharacter and means "zero or more of that char." Because wildcard's * carries no operand, its recurrence is the clean two-way OR dp[i][j-1] || dp[i-1][j] — no j-2skip and no "does the previous char match" guard.

COST Complexity & alternatives

Naive recursion

O(2^n)

Each * branches into many split points.

2D DP table

O(m·n)

O(m·n) time and space; rolling rows → O(n) space.

Greedy O(n) alternative: a two-pointer scan (track the position of the last * and the s index it was anchored at, backtracking only that * when a later mismatch occurs) matches in O(m + n) time and O(1) space. It is trickier to get right than the DP, which is why the table is the safe interview answer.

Pattern transfer → The same 2D "prefix vs prefix" DP table powers Regex Matching (LC 10, where * binds to the preceding char), Edit Distance (LC 72), and Longest Common Subsequence (LC 1143). Whenever you reconcile two strings character-by-character with optional skips, reach for this shape.

RUN IT Fill the dp[i][j] wildcard-matching table

s =p =

step 0 / 26

STARTBuild a (m+1)×(n+1) DP table. dp[i][j] = does s[0..4] match p[0..3]? All cells start false.

1function isMatch(s: string, p: string): boolean {
2  const m = s.length;
3  const n = p.length;
4 
5  // dp[i][j] = true if s[0..i-1] matches p[0..j-1]
6▶  const dp: boolean[][] = Array.from({ length: m + 1 }, () =>
7▶    new Array(n + 1).fill(false),
8▶  );
9  dp[0][0] = true; // empty string matches empty pattern
10 
11  // empty string matches a leading run of '*'
12  for (let j = 1; j <= n; j++) {
13    if (p[j - 1] === '*') dp[0][j] = dp[0][j - 1];
14  }
15 
16  for (let i = 1; i <= m; i++) {
17    for (let j = 1; j <= n; j++) {
18      const sc = s[i - 1]; // current char of s
19      const pc = p[j - 1]; // current char of p
20 
21      if (pc === '*') {
22        // '*' matches empty (dp[i][j-1]) OR absorbs one more char of s (dp[i-1][j])
23        dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
24      } else if (pc === '?' || pc === sc) {
25        // '?' or exact char: consume one char from each
26        dp[i][j] = dp[i - 1][j - 1];
27      }
28      // else: hard mismatch, dp[i][j] stays false
29    }
30  }
31 
32  return dp[m][n];
33}

Loop state
i: —
j: —
sc (s[i-1]): '—'
pc (p[j-1]): '—'

current cell dp[i][j]source cell(s)chosen / final answer

slowfast

TYPESCRIPT The solution, annotated

isMatch.ts
function isMatch(s: string, p: string): boolean {
  const m = s.length;
  const n = p.length;

  // dp[i][j] = true if s[0..i-1] matches p[0..j-1]
  const dp: boolean[][] = Array.from({ length: m + 1 }, () =>
    new Array(n + 1).fill(false),
  );
  dp[0][0] = true; // empty string matches empty pattern

  // empty string matches a leading run of '*'
  for (let j = 1; j <= n; j++) {
    if (p[j - 1] === '*') dp[0][j] = dp[0][j - 1];
  }

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      const sc = s[i - 1]; // current char of s
      const pc = p[j - 1]; // current char of p

      if (pc === '*') {
        // '*' matches empty (dp[i][j-1]) OR absorbs one more char of s (dp[i-1][j])
        dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
      } else if (pc === '?' || pc === sc) {
        // '?' or exact char: consume one char from each
        dp[i][j] = dp[i - 1][j - 1];
      }
      // else: hard mismatch, dp[i][j] stays false
    }
  }

  return dp[m][n];
}

Reading it block by block

Lines 6–9 — allocate the table. dp is an (m+1) × (n+1) boolean grid where index 0 represents the empty prefix. All cells start false.

Line 10 — base case dp[0][0]. An empty pattern matches an empty string. This seeds every subsequent derivation.

Lines 12–14 — seed the top row. Against the empty string, only a leading run of * can match (each * matches the empty sequence). As soon as a non-* char appears, the rest of the row stays false.

Lines 16–30 — fill the rest. For each (i,j) pair, branch on p[j-1]. A *is the OR of "match empty" (dp[i][j-1]) and "absorb one more char" (dp[i-1][j]). A ? or exact char takes the diagonal dp[i-1][j-1]. Anything else is a mismatch.

Line 32 — answer. dp[m][n] asks: does all of s (length m) match all of p (length n)?

Complexity → O(m·n) time — we fill every cell of the table exactly once with O(1) work. O(m·n) space for the table; reducible to O(n) with a rolling two-row approach since each cell only reads the current and previous rows.

INTERVIEWFollow-ups they'll ask

"Can you solve it in O(n) extra space?" Yes — keep only prev and curr rows, cutting space from O(m·n) to O(n).
"Is there an O(m + n) time, O(1) space solution?" Yes — a greedy two-pointer scan. Remember the index of the last * and the s position it was anchored to; on a later mismatch, backtrack only that * to absorb one more char. Beats the DP on space but is harder to reason about.
"How does this differ from Regex Matching (LC 10)?" There *binds to the preceding char ("zero or more of it") and uses a j-2 skip; here * is standalone and matches any sequence, giving the simpler recurrence dp[i][j-1] || dp[i-1][j].
"Edge cases?" Empty s with pattern **** (should be true); pattern "" with non-empty s (false); a pattern that is all * (always true).

OPTIMAL 2D DP

isMatch.ts
function isMatch(s: string, p: string): boolean {
  const m = s.length;
  const n = p.length;

  // dp[i][j] = true if s[0..i-1] matches p[0..j-1]
  const dp: boolean[][] = Array.from({ length: m + 1 }, () =>
    new Array(n + 1).fill(false),
  );
  dp[0][0] = true; // empty string matches empty pattern

  // empty string matches a leading run of '*'
  for (let j = 1; j <= n; j++) {
    if (p[j - 1] === '*') dp[0][j] = dp[0][j - 1];
  }

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      const sc = s[i - 1]; // current char of s
      const pc = p[j - 1]; // current char of p

      if (pc === '*') {
        // '*' matches empty (dp[i][j-1]) OR absorbs one more char of s (dp[i-1][j])
        dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
      } else if (pc === '?' || pc === sc) {
        // '?' or exact char: consume one char from each
        dp[i][j] = dp[i - 1][j - 1];
      }
      // else: hard mismatch, dp[i][j] stays false
    }
  }

  return dp[m][n];
}

ALT 1 Greedy two-pointer with star backtracking

O(m·n) worst case · O(m+n) typical · O(1) space

The slick interview answer — scan both strings once, and whenever you hit a mismatch, rewind to the most recent * and let it swallow one more character.

approach-2.ts
function isMatch(s: string, p: string): boolean {
  const m = s.length;
  const n = p.length;

  let i = 0; // pointer into s
  let j = 0; // pointer into p
  let starJ = -1; // index in p of the most recent '*', or -1 if none seen
  let matchI = 0; // index in s that the '*' is currently anchored to

  while (i < m) {
    if (j < n && (p[j] === '?' || p[j] === s[i])) {
      // '?' or exact char: consume one from each side
      i++;
      j++;
    } else if (j < n && p[j] === '*') {
      // record this '*' and assume it matches the empty sequence for now
      starJ = j;
      matchI = i;
      j++;
    } else if (starJ !== -1) {
      // mismatch: backtrack to the last '*' and let it absorb one more char of s
      j = starJ + 1;
      matchI++;
      i = matchI;
    } else {
      // mismatch with no '*' to fall back on
      return false;
    }
  }

  // s is exhausted; any trailing pattern must be all '*' to still match
  while (j < n && p[j] === '*') j++;

  return j === n;
}

Note → Only the single most-recent * is ever rewound, so even though the worst case (e.g. s="aaaa…", p="*a*a…") is O(m·n), real inputs run in near linear time with no DP table at all — the big win is O(1) space.

ALT 2 Top-down recursion + memoization

O(m·n) time · O(m·n) space

The DP recurrence expressed directly as a recursive function over (i, j), with a memo table to collapse the exponential blowup.

approach-3.ts
function isMatch(s: string, p: string): boolean {
  const m = s.length;
  const n = p.length;

  // memo[i][j]: cached result of match(i, j); undefined = not yet computed
  const memo: (boolean | undefined)[][] = Array.from(
    { length: m + 1 },
    () => new Array<boolean | undefined>(n + 1).fill(undefined),
  );

  // does s[i..] match p[j..] ?
  function match(i: number, j: number): boolean {
    if (memo[i][j] !== undefined) return memo[i][j] as boolean;

    let result: boolean;
    if (j === n) {
      // pattern exhausted: only succeeds if s is also exhausted
      result = i === m;
    } else if (p[j] === '*') {
      // '*' matches empty (advance j) OR absorbs s[i] (advance i, keep j)
      result =
        match(i, j + 1) || (i < m && match(i + 1, j));
    } else {
      // '?' or exact char: consume one from each side
      result = i < m && (p[j] === '?' || p[j] === s[i]) && match(i + 1, j + 1);
    }

    memo[i][j] = result;
    return result;
  }

  return match(0, 0);
}

Note → Each (i, j) state is solved once and cached, so the work is bounded by the number of states — exactly the O(m·n) of the bottom-up table, just driven top-down from the start of both strings.

ALT 3 Plain recursion (no memo)

O(2^(m+n)) time · O(m+n) stack space

The same recurrence with the memo removed — exponential, shown only to highlight how much the cache buys you.

approach-4.ts
function isMatch(s: string, p: string): boolean {
  const m = s.length;
  const n = p.length;

  // does s[i..] match p[j..] ?
  function match(i: number, j: number): boolean {
    if (j === n) {
      // pattern exhausted: only succeeds if s is also exhausted
      return i === m;
    }

    if (p[j] === '*') {
      // '*' matches empty (advance j) OR absorbs s[i] (advance i, keep j)
      return match(i, j + 1) || (i < m && match(i + 1, j));
    }

    // '?' or exact char: consume one from each side
    return i < m && (p[j] === '?' || p[j] === s[i]) && match(i + 1, j + 1);
  }

  return match(0, 0);
}

Note → With no memo, every * re-explores overlapping splits, so a pattern like "*a*a*a*" against a long string of as blows up exponentially. Correct, but unusable beyond tiny inputs.

MNEMONIC The one-liner

"'*' forks two ways: match empty (dp[i][j-1]) OR absorb one more char (dp[i-1][j]). '?' or exact takes the diagonal."

TRIGGERS When you see _ → reach for _

"does the whole string match a glob/wildcard pattern"	2D DP over s and p prefixes
"? = any single char, * = any sequence (incl. empty)"	dp[i][j] = does s[0..i-1] match p[0..j-1]
"standalone * (not bound to preceding char)"	dp[i][j] = dp[i][j-1] \|\| dp[i-1][j]
"related: Regex Matching, Edit Distance, LCS"	same two-string prefix DP shape

SKELETON The reusable shape

skeleton.ts
const m = s.length, n = p.length;
const dp: boolean[][] = Array.from({ length: m + 1 }, () =>
  new Array(n + 1).fill(false));
dp[0][0] = true;
for (let j = 1; j <= n; j++)
  if (p[j-1] === '*') dp[0][j] = dp[0][j-1];

for (let i = 1; i <= m; i++) {
  for (let j = 1; j <= n; j++) {
    if (p[j-1] === '*')
      dp[i][j] = dp[i][j-1] || dp[i-1][j]; // empty OR absorb
    else if (p[j-1] === '?' || p[j-1] === s[i-1])
      dp[i][j] = dp[i-1][j-1];             // match one
  }
}
return dp[m][n];

FLASHCARDS Tap to flip

What does dp[i][j] represent?

true if s[0..i-1] (first i chars) is fully matched by p[0..j-1] (first j chars).

tap to flip

1 / 8

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

When p[j-1] === '*', what is the recurrence for dp[i][j]?

QUESTION 02

In the * branch, which cell represents "the * absorbs one more character of s"?

QUESTION 03

What is the time complexity of the 2D DP solution for isMatch(s, p)?

QUESTION 04

Trace: s="adceb", p="*a*b". What does isMatch return?

QUESTION 05

How does * in Wildcard Matching (LC 44) differ from * in Regular Expression Matching (LC 10)?

QUESTION 06

Against the empty string, when can dp[0][j] be true for j > 0?

QUESTION 07

How would you reduce space from O(m·n) to O(n)?

QUESTION 08

#44 · Wildcard MatchingGiven a string s and a pattern p with ? (any single char) and * (any sequence, including empty), decide if p matches all of s. A 2D DP table over prefixes of both strings resolves it in O(m*n).Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Build truth about prefixes bottom-up

RECIPE Filling the DP table

COST Complexity & alternatives

RUN IT Fill the dp[i][j] wildcard-matching table

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL 2D DP

ALT 1 Greedy two-pointer with star backtracking

ALT 2 Top-down recursion + memoization

ALT 3 Plain recursion (no memo)

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _