Dynamic Programming
LC #44Hard
Wildcard Matching
Dynamic Programming
AmazonGoogleMetaBloombergProblem
Implement wildcard pattern matching with '?' (any single character) and '*' (any sequence including empty).
dynamic-programmingstringgreedy
Constraints
- ›0 ≤ s.length ≤ 2000
- ›0 ≤ p.length ≤ 2000
- ›s contains only lowercase letters
- ›p contains lowercase letters, '?', and '*'
Example
Input
s = "adceb", p = "*a*b"Output
trueWhy
"*" matches "", "a" matches "a", "*" matches "dce", "b" matches "b"