Solution

Method 1 - Greedy Prefix/Suffix Match

Intuition

The pattern p contains exactly one *, which can match any sequence (including empty) of characters. We can split p into a prefix (before *) and a suffix (after *). For p to match a substring of s, there must exist a substring in s that starts with the prefix and ends with the suffix, with any (possibly empty) string in between.

Approach

Split p into prefix and

Related Tags