03. Wildcard Matching

Difficulty:HardPattern:Greedy Star PointerTime:O(s * p)Space:O(1)

Given an input string s and a pattern p, implement wildcard pattern matching with support for '?' (matches any single character) and '*' (matches any sequence of characters, including empty sequence).

How It Works & Algorithmic Design

Solves using Greedy Two Pointers with Backtracking Positions:

Pointers: sIdx = 0, pIdx = 0, match = 0, starIdx = -1.
Traversal:
- Characters match or p[pIdx] === '?': advance both sIdx++, pIdx++.
- p[pIdx] === '*': save star checkpoint starIdx = pIdx, match = sIdx, advance pIdx++.
- Mismatch after star: reset pIdx = starIdx + 1, advance match++, set sIdx = match.
- Otherwise: mismatch without star $\to$ return false.
Post Check: Skip trailing '*' in pattern. Return sIdx === s.length && pIdx === p.length.

Why This Approach Works Best

Greedy two-pointer pointer tracking with star backtracking runs in $O(|s| \times |p|)$ worst-case and $O(1)$ constant space.

Example Walkthrough

Input: s = "cb", p = "?a"

'?' matches 'c', but 'a' != 'b'.

Output: false

Pattern mismatch.

Answer: Wildcard Matching using Greedy Star Pointers

function isMatch(s, p) {
  let sIdx = 0, pIdx = 0, match = 0, starIdx = -1;
  while (sIdx < s.length) {
    if (pIdx < p.length && (p[pIdx] === '?' || s[sIdx] === p[pIdx])) {
      sIdx++; pIdx++;
    } else if (pIdx < p.length && p[pIdx] === '*') {
      starIdx = pIdx; match = sIdx; pIdx++;
    } else if (starIdx !== -1) {
      pIdx = starIdx + 1; match++; sIdx = match;
    } else return false;
  }
  while (pIdx < p.length && p[pIdx] === '*') pIdx++;
  return pIdx === p.length;
}

💡 Match string characters and track last star pattern index for constant-space backtracking.

Key Takeaways

Wildcard '*' matches any sequence without needing a predecessor.
Greedy star position tracking achieves $O(1)$ space complexity.
Significantly faster in practice compared to 2D DP table recursion.