Pattern Matching With Dot and Star

You are given a string s and a pattern pattern, both made of lowercase English letters, plus two special characters that can appear in pattern:

• . matches any single character.
• * matches zero or more of the character immediately before it.

Return whether pattern matches the entire string s, not just part of it. You can assume pattern is well-formed: * never appears as the first character of pattern, and never appears twice in a row.

Examples

Example 1

Input: s = "aa", pattern = "a"
Output: false
Explanation: "a" only matches a single character, but s has two.

Example 2

Input: s = "aa", pattern = "a*"
Output: true
Explanation: "a*" means zero or more "a"s, which covers "aa".

Example 3

Input: s = "ab", pattern = ".*"
Output: true
Explanation: ".*" means zero or more of any character, which covers any string.