#198HardDynamic Programming· Two-String DP (Pattern Matching)

Wildcard Pattern Matcher

A log-filtering tool understands a tiny pattern language: - a lowercase letter matches exactly that letter, - `.` matches any single lowercase letter, - `*` matches **zero or more copies of the item right before it** (the item is a letter or `.`). A pattern **matches** a text only if it matches the **entire** text, not just a part of it. Given `text` and `pattern`, return `true` if the pattern matches the whole text, otherwise `false`. In every pattern, each `*` follows a letter or a `.` (it is never first, and there are no two stars in a row).

Input format

`text`: a string of lowercase letters (possibly empty); `pattern`: a string of lowercase letters, `.` and `*` as described.

Output format

`true` if the pattern matches the entire text, otherwise `false`.

Examples

Input: text = "aa", pattern = "a"

Output: false

The pattern matches only one "a", but the whole text has two.

Input: text = "aab", pattern = "c*a*b"

Output: true

"c*" matches zero c's, "a*" matches "aa" and "b" matches "b".

Input: text = "mississippi", pattern = "mis*is*p*."

Output: false

The final "p*." cannot cover "ippi" together with the earlier parts, so the pattern fails.

Constraints

0 <= text.length <= 300
1 <= pattern.length <= 300
text contains only lowercase letters.
pattern contains lowercase letters, . and *; every * is preceded by a letter or a dot.

#dynamic-programming
#strings
#pattern-matching
#recursion