Wildcard Matching :
Difficulty Level : Medium
Submissions : 340
Asked In :
Marks :10
: 2 | : 0
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:
'?' Matches any single character.
'*' Matches any sequence of characters. ( zero or more )
The matching should cover the entire input string.
Input
First line contains a single string corresponding to 's'.
Second line contains a single string corresponding to 'p'.
Constraints
$$$ 1 \le |s| \le 2000 $$$
$$$ 1 \le |p| \le 2000 $$$
Output
Print either "YES" or "NO"
Examples
Input
cb ?a
Output
NO
Input
abzzzc a*b*c
Output
YES
Note
Input 1
'?' matches 'c', but the second letter is 'a', which does not match 'b'.
Input 2
The pattern matches perfectly where *1 = " and *2 = 'zzz'
