1072 Advanced

1072-wildcard-matching — Wildcard Matching

Functional Programming

Tutorial

The Problem

Wildcard matching with ? (any single character) and * (any sequence, including empty) is used in file globbing (*.rs matches all Rust files), URL routing (/api/*/users), and command-line pattern matching. Unlike regex's .*, wildcard * matches any sequence including empty — semantically simpler but requiring careful DP handling.

The key difference from regex matching (1071): wildcard * matches any sequence by itself, while regex * requires a preceding character. This makes the DP slightly different.

🎯 Learning Outcomes

• Implement wildcard matching with ? and * using 2D DP

• Understand the difference between wildcard * and regex .*

• Handle * in the DP: dp[i][j] = dp[i-1][j] || dp[i][j-1]

• Implement memoized recursion as an alternative

• Connect to Unix shell globbing and URL router matching

Code Example

#![allow(clippy::all)]
// 1072: Wildcard Matching — '?' and '*' — DP

use std::collections::HashMap;

// Approach 1: Bottom-up DP
fn is_match_dp(s: &str, p: &str) -> bool {
    let s: Vec<char> = s.chars().collect();
    let p: Vec<char> = p.chars().collect();
    let (m, n) = (s.len(), p.len());
    let mut dp = vec![vec![false; n + 1]; m + 1];
    dp[0][0] = true;
    for j in 1..=n {
        if p[j - 1] == '*' {
            dp[0][j] = dp[0][j - 1];
        }
    }
    for i in 1..=m {
        for j in 1..=n {
            if p[j - 1] == '*' {
                dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
            } else if p[j - 1] == '?' || p[j - 1] == s[i - 1] {
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }
    dp[m][n]
}

// Approach 2: Recursive with memoization
fn is_match_memo(s: &str, p: &str) -> bool {
    let s: Vec<char> = s.chars().collect();
    let p: Vec<char> = p.chars().collect();

    fn solve(
        i: usize,
        j: usize,
        s: &[char],
        p: &[char],
        cache: &mut HashMap<(usize, usize), bool>,
    ) -> bool {
        if j == p.len() {
            return i == s.len();
        }
        if i == s.len() {
            return p[j..].iter().all(|&c| c == '*');
        }
        if let Some(&v) = cache.get(&(i, j)) {
            return v;
        }
        let v = if p[j] == '*' {
            solve(i, j + 1, s, p, cache) || solve(i + 1, j, s, p, cache)
        } else if p[j] == '?' || p[j] == s[i] {
            solve(i + 1, j + 1, s, p, cache)
        } else {
            false
        };
        cache.insert((i, j), v);
        v
    }

    let mut cache = HashMap::new();
    solve(0, 0, &s, &p, &mut cache)
}

// Approach 3: Two-pointer greedy (O(m*n) worst case, O(m+n) average)
fn is_match_greedy(s: &str, p: &str) -> bool {
    let s: Vec<char> = s.chars().collect();
    let p: Vec<char> = p.chars().collect();
    let (m, n) = (s.len(), p.len());
    let (mut si, mut pi) = (0usize, 0usize);
    let mut star_idx: Option<usize> = None;
    let mut match_idx = 0usize;

    while si < m {
        if pi < n && (p[pi] == '?' || p[pi] == s[si]) {
            si += 1;
            pi += 1;
        } else if pi < n && p[pi] == '*' {
            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[pi] == '*' {
        pi += 1;
    }
    pi == n
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_dp() {
        assert!(is_match_dp("adceb", "*a*b"));
        assert!(!is_match_dp("acdcb", "a*c?b"));
        assert!(is_match_dp("", "*"));
        assert!(!is_match_dp("cb", "?a"));
        assert!(is_match_dp("aa", "*"));
    }

    #[test]
    fn test_memo() {
        assert!(is_match_memo("adceb", "*a*b"));
        assert!(!is_match_memo("acdcb", "a*c?b"));
    }

    #[test]
    fn test_greedy() {
        assert!(is_match_greedy("adceb", "*a*b"));
        assert!(!is_match_greedy("acdcb", "a*c?b"));
        assert!(is_match_greedy("", "*"));
    }
}

(* 1072: Wildcard Matching — '?' and '*' — DP *)

(* Approach 1: Bottom-up DP *)
let is_match_dp s p =
  let m = String.length s and n = String.length p in
  let dp = Array.init (m + 1) (fun _ -> Array.make (n + 1) false) in
  dp.(0).(0) <- true;
  for j = 1 to n do
    if p.[j - 1] = '*' then dp.(0).(j) <- dp.(0).(j - 1)
  done;
  for i = 1 to m do
    for j = 1 to n do
      if p.[j - 1] = '*' then
        dp.(i).(j) <- dp.(i - 1).(j) || dp.(i).(j - 1)
      else if p.[j - 1] = '?' || p.[j - 1] = s.[i - 1] then
        dp.(i).(j) <- dp.(i - 1).(j - 1)
    done
  done;
  dp.(m).(n)

(* Approach 2: Recursive with memoization *)
let is_match_memo s p =
  let m = String.length s and n = String.length p in
  let cache = Hashtbl.create 64 in
  let rec solve i j =
    if j = n then i = m
    else if i = m then
      (* remaining pattern must be all '*' *)
      let all_star = ref true in
      for k = j to n - 1 do
        if p.[k] <> '*' then all_star := false
      done;
      !all_star
    else
      match Hashtbl.find_opt cache (i, j) with
      | Some v -> v
      | None ->
        let v =
          if p.[j] = '*' then
            solve i (j + 1) || solve (i + 1) j
          else if p.[j] = '?' || p.[j] = s.[i] then
            solve (i + 1) (j + 1)
          else
            false
        in
        Hashtbl.add cache (i, j) v;
        v
  in
  solve 0 0

(* Approach 3: Two-pointer greedy *)
let is_match_greedy s p =
  let m = String.length s and n = String.length p in
  let si = ref 0 and pi = ref 0 in
  let star_idx = ref (-1) and match_idx = ref 0 in
  while !si < m do
    if !pi < n && (p.[!pi] = '?' || p.[!pi] = s.[!si]) then begin
      incr si; incr pi
    end else if !pi < n && p.[!pi] = '*' then begin
      star_idx := !pi;
      match_idx := !si;
      incr pi
    end else if !star_idx >= 0 then begin
      pi := !star_idx + 1;
      incr match_idx;
      si := !match_idx
    end else
      (* Mismatch *)
      si := m + 1  (* force exit with failure *)
  done;
  while !pi < n && p.[!pi] = '*' do incr pi done;
  !si = m && !pi = n

let () =
  assert (is_match_dp "adceb" "*a*b" = true);
  assert (is_match_dp "acdcb" "a*c?b" = false);
  assert (is_match_dp "" "*" = true);
  assert (is_match_dp "cb" "?a" = false);
  assert (is_match_dp "aa" "a" = false);
  assert (is_match_dp "aa" "*" = true);

  assert (is_match_memo "adceb" "*a*b" = true);
  assert (is_match_memo "acdcb" "a*c?b" = false);

  assert (is_match_greedy "adceb" "*a*b" = true);
  assert (is_match_greedy "acdcb" "a*c?b" = false);
  assert (is_match_greedy "" "*" = true);

  Printf.printf "✓ All tests passed\n"

Key Differences

*** semantics**: Wildcard * matches any sequence standalone; regex * requires a preceding character. This changes the border initialization and * case.

Simpler DP: Wildcard DP is slightly simpler — the * case is one || without the prefix character check needed for regex.

Globbing: Unix file globbing uses this semantics; *.rs = * + .rs where * matches any sequence.

**Two-state ***: The dp[i-1][j] || dp[i][j-1] for * encodes "match one more char" vs "treat as empty" — a two-state automaton step.

OCaml Approach

let is_match s p =
  let s = Array.of_seq (String.to_seq s) in
  let p = Array.of_seq (String.to_seq p) in
  let m, n = Array.length s, Array.length p in
  let dp = Array.make_matrix (m+1) (n+1) false in
  dp.(0).(0) <- true;
  for j = 1 to n do
    if p.(j-1) = '*' then dp.(0).(j) <- dp.(0).(j-1)
  done;
  for i = 1 to m do
    for j = 1 to n do
      dp.(i).(j) <- if p.(j-1) = '*' then dp.(i-1).(j) || dp.(i).(j-1)
        else (p.(j-1) = '?' || p.(j-1) = s.(i-1)) && dp.(i-1).(j-1)
    done
  done;
  dp.(m).(n)

Identical recurrence with different * semantics than regex matching.

Full Source

#![allow(clippy::all)]
// 1072: Wildcard Matching — '?' and '*' — DP

use std::collections::HashMap;

// Approach 1: Bottom-up DP
fn is_match_dp(s: &str, p: &str) -> bool {
    let s: Vec<char> = s.chars().collect();
    let p: Vec<char> = p.chars().collect();
    let (m, n) = (s.len(), p.len());
    let mut dp = vec![vec![false; n + 1]; m + 1];
    dp[0][0] = true;
    for j in 1..=n {
        if p[j - 1] == '*' {
            dp[0][j] = dp[0][j - 1];
        }
    }
    for i in 1..=m {
        for j in 1..=n {
            if p[j - 1] == '*' {
                dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
            } else if p[j - 1] == '?' || p[j - 1] == s[i - 1] {
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }
    dp[m][n]
}

// Approach 2: Recursive with memoization
fn is_match_memo(s: &str, p: &str) -> bool {
    let s: Vec<char> = s.chars().collect();
    let p: Vec<char> = p.chars().collect();

    fn solve(
        i: usize,
        j: usize,
        s: &[char],
        p: &[char],
        cache: &mut HashMap<(usize, usize), bool>,
    ) -> bool {
        if j == p.len() {
            return i == s.len();
        }
        if i == s.len() {
            return p[j..].iter().all(|&c| c == '*');
        }
        if let Some(&v) = cache.get(&(i, j)) {
            return v;
        }
        let v = if p[j] == '*' {
            solve(i, j + 1, s, p, cache) || solve(i + 1, j, s, p, cache)
        } else if p[j] == '?' || p[j] == s[i] {
            solve(i + 1, j + 1, s, p, cache)
        } else {
            false
        };
        cache.insert((i, j), v);
        v
    }

    let mut cache = HashMap::new();
    solve(0, 0, &s, &p, &mut cache)
}

// Approach 3: Two-pointer greedy (O(m*n) worst case, O(m+n) average)
fn is_match_greedy(s: &str, p: &str) -> bool {
    let s: Vec<char> = s.chars().collect();
    let p: Vec<char> = p.chars().collect();
    let (m, n) = (s.len(), p.len());
    let (mut si, mut pi) = (0usize, 0usize);
    let mut star_idx: Option<usize> = None;
    let mut match_idx = 0usize;

    while si < m {
        if pi < n && (p[pi] == '?' || p[pi] == s[si]) {
            si += 1;
            pi += 1;
        } else if pi < n && p[pi] == '*' {
            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[pi] == '*' {
        pi += 1;
    }
    pi == n
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_dp() {
        assert!(is_match_dp("adceb", "*a*b"));
        assert!(!is_match_dp("acdcb", "a*c?b"));
        assert!(is_match_dp("", "*"));
        assert!(!is_match_dp("cb", "?a"));
        assert!(is_match_dp("aa", "*"));
    }

    #[test]
    fn test_memo() {
        assert!(is_match_memo("adceb", "*a*b"));
        assert!(!is_match_memo("acdcb", "a*c?b"));
    }

    #[test]
    fn test_greedy() {
        assert!(is_match_greedy("adceb", "*a*b"));
        assert!(!is_match_greedy("acdcb", "a*c?b"));
        assert!(is_match_greedy("", "*"));
    }
}

(* 1072: Wildcard Matching — '?' and '*' — DP *)

(* Approach 1: Bottom-up DP *)
let is_match_dp s p =
  let m = String.length s and n = String.length p in
  let dp = Array.init (m + 1) (fun _ -> Array.make (n + 1) false) in
  dp.(0).(0) <- true;
  for j = 1 to n do
    if p.[j - 1] = '*' then dp.(0).(j) <- dp.(0).(j - 1)
  done;
  for i = 1 to m do
    for j = 1 to n do
      if p.[j - 1] = '*' then
        dp.(i).(j) <- dp.(i - 1).(j) || dp.(i).(j - 1)
      else if p.[j - 1] = '?' || p.[j - 1] = s.[i - 1] then
        dp.(i).(j) <- dp.(i - 1).(j - 1)
    done
  done;
  dp.(m).(n)

(* Approach 2: Recursive with memoization *)
let is_match_memo s p =
  let m = String.length s and n = String.length p in
  let cache = Hashtbl.create 64 in
  let rec solve i j =
    if j = n then i = m
    else if i = m then
      (* remaining pattern must be all '*' *)
      let all_star = ref true in
      for k = j to n - 1 do
        if p.[k] <> '*' then all_star := false
      done;
      !all_star
    else
      match Hashtbl.find_opt cache (i, j) with
      | Some v -> v
      | None ->
        let v =
          if p.[j] = '*' then
            solve i (j + 1) || solve (i + 1) j
          else if p.[j] = '?' || p.[j] = s.[i] then
            solve (i + 1) (j + 1)
          else
            false
        in
        Hashtbl.add cache (i, j) v;
        v
  in
  solve 0 0

(* Approach 3: Two-pointer greedy *)
let is_match_greedy s p =
  let m = String.length s and n = String.length p in
  let si = ref 0 and pi = ref 0 in
  let star_idx = ref (-1) and match_idx = ref 0 in
  while !si < m do
    if !pi < n && (p.[!pi] = '?' || p.[!pi] = s.[!si]) then begin
      incr si; incr pi
    end else if !pi < n && p.[!pi] = '*' then begin
      star_idx := !pi;
      match_idx := !si;
      incr pi
    end else if !star_idx >= 0 then begin
      pi := !star_idx + 1;
      incr match_idx;
      si := !match_idx
    end else
      (* Mismatch *)
      si := m + 1  (* force exit with failure *)
  done;
  while !pi < n && p.[!pi] = '*' do incr pi done;
  !si = m && !pi = n

let () =
  assert (is_match_dp "adceb" "*a*b" = true);
  assert (is_match_dp "acdcb" "a*c?b" = false);
  assert (is_match_dp "" "*" = true);
  assert (is_match_dp "cb" "?a" = false);
  assert (is_match_dp "aa" "a" = false);
  assert (is_match_dp "aa" "*" = true);

  assert (is_match_memo "adceb" "*a*b" = true);
  assert (is_match_memo "acdcb" "a*c?b" = false);

  assert (is_match_greedy "adceb" "*a*b" = true);
  assert (is_match_greedy "acdcb" "a*c?b" = false);
  assert (is_match_greedy "" "*" = true);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_dp() {
        assert!(is_match_dp("adceb", "*a*b"));
        assert!(!is_match_dp("acdcb", "a*c?b"));
        assert!(is_match_dp("", "*"));
        assert!(!is_match_dp("cb", "?a"));
        assert!(is_match_dp("aa", "*"));
    }

    #[test]
    fn test_memo() {
        assert!(is_match_memo("adceb", "*a*b"));
        assert!(!is_match_memo("acdcb", "a*c?b"));
    }

    #[test]
    fn test_greedy() {
        assert!(is_match_greedy("adceb", "*a*b"));
        assert!(!is_match_greedy("acdcb", "a*c?b"));
        assert!(is_match_greedy("", "*"));
    }
}

Deep Comparison

Wildcard Matching — Comparison

Core Insight

Wildcard * matches any sequence (including empty), simpler than regex *. The DP recurrence: * → dp[i-1][j] || dp[i][j-1]. The greedy two-pointer approach remembers the last * position and backtracks there on mismatch.

OCaml Approach

• 2D boolean array DP — same structure as regex matching

• Greedy: ref cells for pointers and star position

• while loop with ref mutation for pointer advancement

• Force-exit trick: si := m + 1 to break while loop

Rust Approach

• 2D vec![vec![false]] DP

• Greedy: Option<usize> for star position — cleaner than -1 sentinel

• if let Some(star) = star_idx for safe star backtrack

• Slice p[j..].iter().all() for remaining-all-stars check

Comparison Table

Aspect	OCaml	Rust
Star sentinel	`ref (-1)`	`Option<usize>`
All-stars check	`ref` flag + loop	`.iter().all(\\|&c\\| c == '*')`
Loop exit	`si := m + 1` (hack)	`return false`
Pointer advance	`incr si; incr pi`	`si += 1; pi += 1`
DP structure	Identical recurrence	Identical recurrence

Exercises

Add support for [abc] character classes that match any character in the set.

Implement glob_files(pattern: &str, files: &[&str]) -> Vec<&str> using wildcard matching to filter a file list.

Write a URL router using wildcard matching: Route { pattern: &str, handler: fn(&str) } with match_route(url: &str, routes: &[Route]) -> Option<&Route>.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust