Wildcard matching

String Dynamic Programming Greedy Recursion

31.4% acceptance

Jan 12, 2026

9077

416

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where: '?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence). The matching should cover the entire input string (not partial).

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn is_match_wildcard(s: String, p: String) -> bool {
    let s_bytes = s.as_bytes();
    let p_bytes = p.as_bytes();
    let m = s_bytes.len();
    let n = p_bytes.len();
    
    let mut si = 0;
    let mut pi = 0;
    let mut star_idx = None;
    let mut match_idx = 0;
    
    while si < m {
      if pi < n && (p_bytes[pi] == b'?' || p_bytes[pi] == s_bytes[si]) {
        si += 1;
        pi += 1;
      } else if pi < n && p_bytes[pi] == b'*' {
        star_idx = Some(pi);
        match_idx = si;
        pi += 1;
      } else if let Some(star) = star_idx {
        pi = star + 1;
        match_idx += 1;
        si = match_idx;
      } else {
        return false;
      }
    }
    
    while pi < n && p_bytes[pi] == b'*' {
      pi += 1;
    }
    
    pi == n
  }
}