Problem

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

1
2
3
4
5

Input: s = "abaacbaecebce", p = "ba*c*ce"
Output: 8
Explanation:
The shortest matching substring of `p` in `s` is `"_**ba**_ e _**c**_ eb
_**ce**_ "`.

Example 2

1
2
3
4

Input: s = "baccbaadbc", p = "cc*baa*adb"
Output: -1
Explanation:
There is no matching substring in `s`.

Example 3

1
2
3
4

Input: s = "a", p = "**"
Output: 0
Explanation:
The empty substring is the shortest matching substring.

Example 4

1
2
3
4

Input: s = "madlogic", p = "*adlogi*"
Output: 6
Explanation:
The shortest matching substring of `p` in `s` is `"**_adlogi_** "`.

Constraints

  • 1 <= s.length <= 10^5
  • 2 <= p.length <= 10^5
  • s contains only lowercase English letters.
  • p contains only lowercase English letters and exactly two '*'.

Examples

Solution

Method 1 – Two-Pointer + Prefix/Suffix Matching

Intuition

Since the pattern has exactly two ‘’, we can split it into three parts: prefix, middle, and suffix. For each possible split in s, check if the prefix and suffix match, and the middle part (between the two ‘’) can be matched in order.

Approach

  1. Split p into three parts: pre, mid, suf by the two ‘*’.
  2. For each position in s, find all possible matches for pre (from left) and suf (from right).
  3. For each valid pair (end of pre, start of suf), check if mid can be matched in order between them.
  4. Track the minimum length.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    int shortestMatchingSubstring(string s, string p) {
        int n = s.size(), m = p.size();
        int a = p.find('*'), b = p.rfind('*');
        string pre = p.substr(0,a), mid = p.substr(a+1,b-a-1), suf = p.substr(b+1);
        vector<int> preEnd, sufStart;
        // Prefix match
        for (int i=0; i+pre.size()<=n; ++i) {
            if (s.substr(i,pre.size())==pre) preEnd.push_back(i+pre.size()-1);
        }
        // Suffix match
        for (int i=0; i+suf.size()<=n; ++i) {
            if (s.substr(i,suf.size())==suf) sufStart.push_back(i);
        }
        int res = 1e9;
        for (int l:preEnd) for (int r:sufStart) if (l<r) {
            // Check mid in s[l+1..r-1]
            int i=l+1, j=0;
            while (i<r && j<mid.size()) {
                if (s[i]==mid[j]) ++j;
                ++i;
            }
            if (j==mid.size()) res = min(res, r-l+1);
        }
        if (pre.empty() && suf.empty() && mid.empty()) return 0;
        return res==1e9?-1:res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import java.util.*;
class Solution {
    public int shortestMatchingSubstring(String s, String p) {
        int n = s.length(), m = p.length();
        int a = p.indexOf('*'), b = p.lastIndexOf('*');
        String pre = p.substring(0,a), mid = p.substring(a+1,b), suf = p.substring(b+1);
        List<Integer> preEnd = new ArrayList<>(), sufStart = new ArrayList<>();
        for (int i=0; i+pre.length()<=n; ++i)
            if (s.substring(i,i+pre.length()).equals(pre)) preEnd.add(i+pre.length()-1);
        for (int i=0; i+suf.length()<=n; ++i)
            if (s.substring(i,i+suf.length()).equals(suf)) sufStart.add(i);
        int res = Integer.MAX_VALUE;
        for (int l:preEnd) for (int r:sufStart) if (l<r) {
            int i=l+1, j=0;
            while (i<r && j<mid.length()) {
                if (s.charAt(i)==mid.charAt(j)) ++j;
                ++i;
            }
            if (j==mid.length()) res = Math.min(res, r-l+1);
        }
        if (pre.isEmpty() && suf.isEmpty() && mid.isEmpty()) return 0;
        return res==Integer.MAX_VALUE?-1:res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def shortestMatchingSubstring(self, s: str, p: str) -> int:
        a, b = p.find('*'), p.rfind('*')
        pre, mid, suf = p[:a], p[a+1:b], p[b+1:]
        n = len(s)
        preEnd = [i+len(pre)-1 for i in range(n-len(pre)+1) if s[i:i+len(pre)]==pre]
        sufStart = [i for i in range(n-len(suf)+1) if s[i:i+len(suf)]==suf]
        res = float('inf')
        for l in preEnd:
            for r in sufStart:
                if l < r:
                    i, j = l+1, 0
                    while i < r and j < len(mid):
                        if s[i]==mid[j]: j+=1
                        i+=1
                    if j==len(mid):
                        res = min(res, r-l+1)
        if not pre and not suf and not mid:
            return 0
        return -1 if res==float('inf') else res

Complexity

  • ⏰ Time complexity: O(n*m) — For each prefix and suffix match, we may scan the substring for the middle part.
  • 🧺 Space complexity: O(n) — For storing prefix and suffix match positions.