Substring Matching Pattern - Solution & Explanation
Problem Statement
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.
Example 1:
Input: s = "leetcode", p = "ee*e"
Output: true
Explanation:
By replacing the '*' with "tcod", the substring "eetcode" matches the pattern.
Example 2:
Input: s = "car", p = "c*v"
Output: false
Explanation:
There is no substring matching the pattern.
Example 3:
Input: s = "luck", p = "u*"
Output: true
Explanation:
The substrings "u", "uc", and "uck" match the pattern.
Constraints:
1 <= s.length <= 501 <= p.length <= 50scontains only lowercase English letters.pcontains only lowercase English letters and exactly one'*'
Approach Overview
Problem Overview: You are given a text string s and a pattern p. The pattern contains lowercase characters and a wildcard * that can match any sequence of characters (including empty). The task is to determine whether some substring of s matches the pattern.
Approach 1: Brute Force Substring Check (O(n^3) time, O(1) space)
Generate every possible substring of s using two nested loops for the start and end index. For each substring, check whether it matches the pattern by simulating the wildcard behavior. When the pattern contains *, split it logically and test whether the substring starts with the prefix and ends with the suffix. This approach is easy to reason about but inefficient because substring generation is O(n^2) and each comparison may take up to O(n). It works only for very small inputs but helps you understand the structure of the problem.
Approach 2: Prefix–Suffix String Matching (O(n) time, O(1) space)
The key observation is that the pattern contains a wildcard that can represent any sequence. Split the pattern around * into two parts: prefix and suffix. A valid substring must start with prefix and later end with suffix. Scan the string to find occurrences of the prefix, then check whether the suffix appears at or after the position where the prefix match ends. Because each scan is linear, the total runtime stays O(n). This method relies purely on string operations such as substring comparison and index scanning.
Implementation typically checks edge cases first. If the prefix is empty, only the suffix must appear somewhere in the string. If the suffix is empty, only the prefix must appear. Otherwise, iterate through the string and compare characters to confirm the prefix match, then verify the suffix occurs later. This approach is simple, cache-friendly, and performs well in interviews and production code.
Approach 3: String Matching with KMP (O(n + m) time, O(m) space)
For very large inputs or repeated queries, you can use a classic string matching algorithm such as KMP. First search for all occurrences of the prefix using KMP preprocessing. Then search for suffix occurrences and ensure at least one suffix appears after a prefix match. KMP avoids repeated character comparisons and guarantees linear time relative to the text and pattern length.
Recommended for interviews: The prefix–suffix scan is the expected solution. It demonstrates that you recognized the wildcard structure and reduced the problem to simple string comparisons. Mentioning the brute force approach shows baseline reasoning, but implementing the linear scan proves you can optimize string matching problems efficiently.
Solution
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.
Therefore, we first initialize a pointer i to the start of string s, then iterate over each substring t obtained by splitting the pattern string p by *. For each t, we search for it in s starting from position i. If it is found, we move the pointer i to the end of t and continue searching for the next substring. If it is not found, it means the pattern string p cannot become a substring of s, and we return false. If all substrings are found, we return true.
The time complexity is O(n times m), and the space complexity is O(m), where n and m are the lengths of strings s and p, respectively.
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Substring Enumeration | O(n^3) | O(1) | Understanding the problem or testing small inputs |
| Prefix-Suffix Linear Scan | O(n) | O(1) | General solution for interview problems and production code |
| KMP-Based String Matching | O(n + m) | O(m) | Large inputs or repeated pattern searches where preprocessing helps |
Video Solution
3407. Substring Matching Pattern (Leetcode Easy) • Programming Live with Larry • 801 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Substring Matching Pattern easy or hard?
Substring Matching Pattern Python/Java solution
How to solve Substring Matching Pattern in O(n)?
What is the best approach for Substring Matching Pattern?
Is Substring Matching Pattern asked at Google/Amazon/Meta?
What data structure is used in Substring Matching Pattern?
What is the time complexity of Substring Matching Pattern?
Ready to solve this problem?
Practice Substring Matching Pattern with our built-in code editor and test cases.
Practice on FleetCode