We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Shortest Matching Substring

Difficulty: Hard

Problem 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. The empty substring is considered valid.

Key Insights

  • The pattern p contains two wildcards (*), allowing for flexible matching.
  • The key is to identify the fixed parts of p (i.e., characters that are not *) and their positions relative to s.
  • We can utilize two pointers to efficiently explore matching substrings in s.
  • The problem can be approached by identifying all possible positions of the fixed segments in s and calculating the lengths of substrings that can match the pattern.

Space and Time Complexity

Time Complexity: O(n * m), where n is the length of s and m is the length of p. In the worst case, we may have to scan through each character in s for each character in p. Space Complexity: O(1), as we are using a constant amount of space for pointers and indices.

Solution

To solve this problem, we can use a two-pointer approach to find all occurrences of the fixed parts of the pattern in the string s. We will also account for the two '*' characters in the pattern, which can match any number of characters (including zero). By keeping track of the minimum length of valid substrings that match the pattern, we can efficiently determine the shortest matching substring.

  1. Identify the segments of p between the '*' characters.
  2. Iterate through s using two pointers to find matching segments.
  3. Calculate the length of valid substrings that match the pattern and update the minimum length found.

Code Solutions

def shortest_matching_substring(s: str, p: str) -> int:
    # Extract the fixed parts of the pattern
    parts = p.split('*')
    
    if len(parts) != 3:
        return -1  # Since there must be exactly two '*' in p
    
    part1, part2, part3 = parts
    min_length = float('inf')
    
    # Find the starting positions of part1 in s
    start = 0
    while start <= len(s) - len(part1):
        start = s.find(part1, start)
        if start == -1:
            break
        
        # Find the ending positions of part3 in s after part1
        end = start + len(part1)
        while end <= len(s) - len(part3):
            end = s.find(part3, end)
            if end == -1:
                break
            
            # Check the middle part (part2) from the end of part1 to start of part3
            middle = s[start + len(part1):end]
            if len(middle) >= len(part2):
                min_length = min(min_length, end + len(part3) - start)
            else:
                # If part2 is not found, we can try to include more characters
                # in the middle while still looking for part3
                for i in range(len(middle) + 1):
                    if len(middle[i:]) >= len(part2):
                        min_length = min(min_length, end + len(part3) - start)
                        break
            
            end += 1  # Move to the next character after found part3
        
        start += 1  # Move to the next character after found part1
    
    return min_length if min_length != float('inf') else -1
← Back to All Questions