All problems

Regular Expression Matching

Hard · dynamic programming

You are given a piece of text and a pattern, and must decide whether the pattern describes the whole text. The pattern is written with lowercase letters and two special symbols:

• . stands for any single letter.
• * means that the item just before it (a letter or a .) may be repeated any number of times, including zero. So a* can stand for nothing, a, aa, aaa and so on, and .* can stand for any run of letters.

Return true if the entire text can be produced by the pattern, and false otherwise. Matching only part of the text does not count.

The pattern is always well formed: a * always comes right after a letter or a ., so the pattern never starts with * and never contains **.

Examples

Example 1

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

Output: false

The pattern describes a single letter, but the text has two.

Example 2

Input: text = "shoot", pattern = "sh.*t"

Output: true

s and h match themselves, .* stands for oo, and the final t matches itself.

Example 3

Input: text = "zzy", pattern = "x*z*y"

Output: true

x* stands for nothing, z* stands for zz, and y matches itself.

Constraints

• 0 <= len(text) <= 300
• 0 <= len(pattern) <= 300
• text contains only lowercase English letters.
• pattern contains only lowercase English letters, . and *, and every * follows a letter or a ..