Does the Text Fit the Pattern

Hard

You are given a string text and a pattern pattern. Besides ordinary letters, the pattern may contain two special characters: - ? stands for exactly one character, any character; - * stands for any sequence of characters, including the empty one. An ordinary letter in the pattern matches only itself. The pattern must describe the whole string, not just a part of it. Return True if text fits pattern and False otherwise.

Example 1

text='report', pattern='r*t' → True

The star takes "epor", and the first and last letters match.

Example 2

text='cat', pattern='c?' → False

The pattern describes exactly two letters, while the word has three.

Example 3

text='', pattern='**' → True

Each star may stand for the empty string.

Constraints

0 ≤ text.length, pattern.length ≤ 2000
text consists of lowercase English letters only
pattern consists of lowercase English letters, ? and *

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Recursion String Dynamic Programming

Similar problems

Pattern With Dot and Star Hard Mirror Chunk Split Hard Disjoint Long Palindromes Hard Word From a Prefix Table Hard Largest Palindrome That Is a Multiple Hard

Input

text='report', pattern='r*t'

Expected

True

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