3455. Shortest Matching Substring
SourceBiweekly Contest 150 Q4DifficultyHardRating2303
Description
You are given a string s and a pattern string p, where p contains exactly two '*' characters.
The '*' in p matches any sequence of zero or more characters.
Return the length of the shortest substring in s that matches p. If there is no such substring, return -1.
Note: The empty substring is considered valid.
Example 1:
Input: s = "abaacbaecebce", p = "ba*c*ce"
Output: 8
Explanation:
The shortest matching substring of p in s is "baecebce".
Example 2:
Input: s = "baccbaadbc", p = "cc*baa*adb"
Output: -1
Explanation:
There is no matching substring in s.
Example 3:
Input: s = "a", p = "**"
Output: 0
Explanation:
The empty substring is the shortest matching substring.
Example 4:
Input: s = "madlogic", p = "*adlogi*"
Output: 6
Explanation:
The shortest matching substring of p in s is "adlogi".
Constraints:
1 <= s.length <= 1052 <= p.length <= 105scontains only lowercase English letters.pcontains only lowercase English letters and exactly two'*'.
Solutions
Solution 1
Thinking
\(p\) contains exactly two stars and splits into three literals \(a\), \(b\), \(c\). \(|s|,|p|\le 10^5\) forbids a naive search from every start.
The shortest match is determined by occurrence positions: after one \(a\), take the earliest later \(b\), then the earliest later \(c\).
KMP or Z-algorithm lists every occurrence of the three pieces. A two-pointer sweep over \(a\)'s starts advances \(b\) and \(c\). The length is the right end of \(c\) minus the left end of \(a\), or \(-1\) if none exists.
1 | |
1 | |
1 | |
1 | |