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).