Wildcard Filename Match

Medium2-D Dynamic Programming

Problem

A backup tool selects files with patterns. In a pattern, ? matches exactly one character and * matches any sequence of characters, including the empty one. Every other character matches only itself.

Return true if pattern matches the entire name, otherwise false.

Example 1

Input:
name = "report.txt", pattern = "*.txt"
Output:
true

"*" absorbs "report" and ".txt" matches literally.

Example 2

Input:
name = "data1.csv", pattern = "data?.cs"
Output:
false

The pattern ends at "cs", leaving "v" unmatched.

Example 3

Input:
name = "abc", pattern = "a*?c"
Output:
true

Constraints

  • 0 ≤ name.length, pattern.length ≤ 1000
  • name contains letters, digits and '.'
  • pattern contains letters, digits, '.', '?' and '*'

Hint

Show the first hint

Match prefixes: can the first j pattern characters match the first i name characters?

Walkthrough

How to approach it

01Clarify before coding

  • Must the match cover the whole name? Yes, not just a substring.
  • Can '*' match the empty string? Yes.
  • Are there escape characters? No; '?' and '*' are always wildcards.

02Brute force

Recursively try every possible length for each '*' and check the rest.

Cost: Exponential with several stars: each star tries up to n lengths, and the same (name position, pattern position) pairs are re-explored many times.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.