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

Substring Matching Pattern

Difficulty: Easy

Problem Description

You are given a string s and a pattern string p, where p contains exactly one '' character. The '' in p can be replaced with any sequence of zero or more characters. Return true if p can be made a substring of s, and false otherwise.

Key Insights

  • The pattern p contains exactly one wildcard character '*', which can match any sequence of characters.
  • The substring before the '*' must match the beginning of a substring in s.
  • The substring after the '*' must match the end of a substring in s.
  • By checking all potential split points of s where the prefix and suffix can be derived from p, we can determine if p can match a substring in s.

Space and Time Complexity

Time Complexity: O(n * m), where n is the length of s and m is the length of p. This is due to checking each possible starting position in s for a match with the prefix of p and the suffix of p. Space Complexity: O(1), as we are using a constant amount of space for variables regardless of input size.

Solution

To solve this problem, we will:

  1. Identify the position of the '*' in the pattern p.
  2. Split the pattern into a prefix (before the '') and a suffix (after the '').
  3. Iterate through all possible starting indices in the string s where the prefix can match.
  4. For each starting index, check if the remainder of the string s matches the suffix based on the length of the matched prefix.
  5. If both the prefix and suffix match successfully for any starting position, return true; otherwise, return false.

Code Solutions

def is_substring_matching(s: str, p: str) -> bool:
    star_index = p.index('*')
    prefix = p[:star_index]
    suffix = p[star_index + 1:]

    # Iterate through all possible starting positions for the prefix in s
    for i in range(len(s) - len(prefix) + 1):
        if s[i:i + len(prefix)] == prefix:
            # Check if the suffix can match the end of s
            if s[len(s) - len(suffix):] == suffix or len(suffix) == 0:
                return True
    return False
← Back to All Questions