Given two strings, input_string and pattern_string, determine if pattern_string matches input_string using the following rules: ? matches any single character, * matches any sequence of characters (including the empty sequence). The match must cover the entire input_string.
Example 1
Input: input_string=abcde, pattern_string=a*de
Output: True
Explanation: a*de matches abcde because * can match bc.
Example 2
Input: input_string=xyz, pattern_string=x?z
Output: True
Explanation: x?z matches xyz because ? matches y.
Example 3
Input: input_string=abcd, pattern_string=a*d?
Output: False
Explanation: a*d? does not match abcd because ? requires one more character after d.
Constraints
Case 1
Input: input_string='hello', pattern_string='h*o'
Expected: True
Case 2
Input: input_string='test', pattern_string='t*st'
Expected: True
Case 3
Input: input_string='pattern', pattern_string='p*t?rn'
Expected: True
Case 4
Input: input_string='abc', pattern_string='a*d'
Expected: False
Case 5
Input: input_string='mississippi', pattern_string='m*si*?pi'
Expected: True