Pattern With Dot and Star

Hard

You are given a string text and a pattern pattern. Besides lowercase English letters, the pattern may contain two special characters: - . matches any single character; - * means the character right before it may repeat any number of times, including zero. Return True if the pattern matches the whole of text (not just part of it), and False otherwise.

Example 1

text="moon", pattern="mo*n" → True

o* takes both letters o, and the remaining characters match.

Example 2

text="cat", pattern="c." → False

c. describes exactly two characters, but the text has three, and the pattern must cover all of it.

Example 3

text="bx", pattern="a*b.*" → True

a* takes nothing, b matches b, and .* absorbs the x.

Constraints

0 ≤ len(text) ≤ 20
1 ≤ len(pattern) ≤ 20
text consists of lowercase English letters
pattern consists of lowercase English letters, . and *
Every * is preceded by a letter or .

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Recursion String Dynamic Programming

Similar problems

Does the Text Fit the Pattern Hard Every Bracketing Result Medium Longest Balanced Bracket Stretch Hard Shuffle by Cutting and Swapping Hard Ways to Cross Out Hard

Input

text="moon", pattern="mo*n"

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 136 tests on the server, hidden ones included.