Skills101
← All coding problems

Wildcard Matching

hardDynamic Programming II+40 XPTime limit 2s

A file-search box supports two wildcards in a pattern:

  • ? matches exactly one character
  • * matches any sequence of characters, including the empty one

Does the pattern match the whole text?

Input: two lines: the text s, then the pattern p.

Output: true or false.

Constraints: 1 ≤ length of s, p ≤ 2000; s has lowercase letters, p has lowercase letters, ? and *.

Examples: abcde matches a*d? → true; abc vs a? → false; ab vs * → true.

Think about it: match[i][j] = does s[i:] match p[j:]? A letter or ? must consume one character of each; a * either matches nothing (match[i][j+1]) or eats one more character (match[i+1][j]). O(|s| · |p|). There is also a clever greedy that remembers only the last * seen.

Sample input 1

abcde
a*d?

Sample output 1

true

Sample input 2

abc
a?

Sample output 2

false

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.