Regular Expression Matching

The pattern p may contain . (matches any single character) and * (matches zero or more copies of the character just before it). Return True if p matches the whole string s. A * always follows a letter or ..

For s = "aab" and p = "c*a*b" the answer is True; for s = "mississippi" and p = "mis*is*p*." it is False.

Examples

Example 1

Input:

is_match_regex('aab', 'c*a*b')

Output:

True

Example 2

Input:

is_match_regex('mississippi', 'mis*is*p*.')

Output:

False

Constraints

• 0 <= len(s) <= 1000
• 0 <= len(p) <= 1000
• s has lower-case letters; p has lower-case letters, . and *, and every * has a letter or . before it.