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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Substring Matching Pattern

Number: 3684

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given a string s and a pattern p that contains exactly one '' character (which can match any sequence of zero or more characters), determine whether it is possible to replace '' with a suitable sequence so that the resulting string is a substring of s.

Key Insights

  • Split the pattern into two parts using the '*' as the delimiter: a prefix and a suffix.
  • A candidate substring from s must have a length of at least prefix.length + suffix.length.
  • The candidate substring must start with the prefix and end with the suffix; the '*' can match any characters in between.
  • Since s and p are small (length up to 50), a brute-force iteration over all substrings of s is acceptable.

Space and Time Complexity

Time Complexity: O(n^2 * m) where n is the length of s and m is the combined length of the prefix and suffix; n is up to 50 so the brute-force check is efficient. Space Complexity: O(1) additional space (ignoring the space for the input and output).

Solution

The solution splits the pattern at '*', generating a prefix and a suffix. Then, it iterates over all possible contiguous substrings of s that are at least as long as prefix+suffix. For each substring, the algorithm checks if it begins with the prefix and ends with the suffix. If such a substring is found, the function returns true; otherwise, after checking all candidates, it returns false. This approach leverages simple string matching and iteration with minimal extra space.

Code Solutions

def isMatch(s: str, p: str) -> bool:
    # Split the pattern into prefix and suffix using the '*' character.
    prefix, suffix = p.split('*')
    n = len(s)
    # Iterate over all possible substrings of s.
    for i in range(n):
        # The smallest valid substring must have a length of prefix + suffix.
        for j in range(i + len(prefix) + len(suffix) - 1, n):
            substring = s[i:j+1]
            # Check if the substring starts with 'prefix' and ends with 'suffix'.
            if substring.startswith(prefix) and substring.endswith(suffix):
                return True
    return False

# Testing examples
print(isMatch("leetcode", "ee*e"))  # Expected output: True
print(isMatch("car", "c*v"))        # Expected output: False
print(isMatch("luck", "u*"))         # Expected output: True
← Back to All Questions