#3407

Easy

LeetCode Problem Workspace

Substring Matching Pattern

Determine if a pattern containing a single wildcard can match any substring of a given string efficiently.

Problem Statement

Given a string s and a pattern string p containing exactly one '' character, determine whether any substring of s can match p after replacing ' ' with zero or more characters. The '*' can represent any sequence, including an empty string.

Return true if there exists a substring in s that matches the pattern p, and false otherwise. Examples illustrate cases where multiple substrings can satisfy the pattern or no match exists.

Examples

Example 1

Input: s = "leetcode", p = "ee*e"

Output: true

By replacing the '*' with "tcod" , the substring "eetcode" matches the pattern.

Example 2

Input: s = "car", p = "c*v"

Output: false

There is no substring matching the pattern.

Example 3

Input: s = "luck", p = "u*"

Output: true

The substrings "u" , "uc" , and "uck" match the pattern.

Constraints

1 <= s.length <= 50
1 <= p.length <= 50
s contains only lowercase English letters.
p contains only lowercase English letters and exactly one '*'

Solution Approach

Split pattern at wildcard

Divide the pattern into a prefix before '' and a suffix after ' '. This isolates fixed parts of the pattern to search for exact matches in s.

Scan for matching substrings

Iterate through s and check for substrings where the prefix aligns with the start and the suffix aligns with the end. Ensure substring length is at least the sum of prefix and suffix lengths.

Return match result

If any substring satisfies both prefix and suffix alignment, return true. If no substring matches after full iteration, return false.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on scanning s and checking prefix and suffix matches, roughly O(n * m) where n = s.length and m = p.length. Space complexity is O(1) extra if no substring storage is needed.

What Interviewers Usually Probe

Notice the pattern contains exactly one '*' indicating a split-match approach.
Ask about handling empty matches for the '*' character.
Check if your substring scanning handles all offsets efficiently.

Common Pitfalls or Variants

Common pitfalls

Forgetting that '*' can match zero characters, leading to missed valid matches.
Checking substrings shorter than prefix+suffix, which cannot match.
Incorrectly matching prefix and suffix positions causing false negatives.

Follow-up variants

Patterns containing multiple '*' characters requiring backtracking or DP.
Case-insensitive matching or Unicode string support.
Finding all matching substrings instead of just returning true/false.

FAQ

What does '*' represent in the Substring Matching Pattern problem?

'*' can be replaced by any sequence of characters, including an empty string, in the pattern.

How do I efficiently check substrings against the pattern?

Split the pattern into prefix and suffix and check each substring of sufficient length for alignment with both parts.

Can the pattern match an empty substring?

Only if the prefix and suffix are both empty or if '*' accounts for the entire substring.

What is the time complexity for this approach?

Roughly O(n * m), where n is the length of s and m is the length of p, because each substring may require prefix and suffix checks.

Are there edge cases I should be careful about?

Yes, especially when '*' matches zero characters or when prefix/suffix length is close to s length, requiring careful substring bounds checking.

terminal

Solution

Solution 1: String Matching

According to the problem description, `*` can be replaced by any sequence of zero or more characters, so we can split the pattern string $p$ by `*` into several substrings. If these substrings appear in order in the string $s$, then $p$ can become a substring of $s$.

1

2

3

4

5

6

7

8

9

class Solution:
    def hasMatch(self, s: str, p: str) -> bool:
        i = 0
        for t in p.split("*"):
            j = s.find(t, i)
            if j == -1:
                return False
            i = j + len(t)
        return True

Continue Practicing

#3455 shortest matching substring #3474 lexicographically smallest generated string #3303 find the occurrence of first almost equal substring