Substring Matching Pattern
EasyPrompt
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'*'
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves generating every possible substring of s and checking if it matches the pattern p. A substring matches the pattern if it starts with the pattern's prefix, ends with its suffix, and has a sufficient length.
Algorithm
- First, parse the pattern
pto extract the prefix and suffix parts by finding the*character. Let's call themprefixandsuffix. - Then, iterate through all possible start and end indices of substrings in
s. For each substringsub:- Check if
sub's length is at leastprefix.length() + suffix.length(). - Check if
substarts withprefix. - Check if
subends withsuffix.
- Check if
- If all three conditions are met for any substring, a match is found, and we return
true. - If all substrings are checked and no match is found, we return
false.
Walkthrough
The fundamental idea is to test every single substring of s against the pattern p. We begin by splitting the pattern p at the * character to get a prefix and a suffix. Then, we use two nested loops to generate all substrings of s. The outer loop selects the starting index i, and the inner loop selects the ending index j. For each substring s.substring(i, j), we verify if it could match the pattern. A match is valid if the substring's length is at least the combined length of the prefix and suffix, the substring begins with the prefix, and it ends with the suffix. If we find such a substring, we can immediately conclude that the pattern matches and return true. If the loops complete without finding any such substring, it means no match is possible, and we return false.
class Solution { public boolean matchPattern(String s, String p) { int starIndex = p.indexOf('*'); String prefix = p.substring(0, starIndex); String suffix = p.substring(starIndex + 1); for (int i = 0; i < s.length(); i++) { for (int j = i; j <= s.length(); j++) { String sub = s.substring(i, j); if (sub.length() >= prefix.length() + suffix.length()) { if (sub.startsWith(prefix) && sub.endsWith(suffix)) { return true; } } } } return false; }}Complexity
Time
O(N^3 * M), where N is the length of `s` and M is the length of `p`. The two nested loops give O(N^2) iterations. Inside the loop, creating a substring can take O(N) time, and `startsWith`/`endsWith` can take O(M) time. This results in a very high time complexity.
Space
O(N), where N is the length of `s`. This is for storing the generated substring `sub` in each iteration.
Trade-offs
Pros
Simple to conceptualize and implement.
Directly translates the problem definition into code.
Cons
Highly inefficient due to the generation and checking of all O(N^2) substrings.
Likely to result in a 'Time Limit Exceeded' error for the given constraints.
This approach improves upon the brute-force method by avoiding the generation of all substrings. Instead, it searches for occurrences of the prefix in s. For each found prefix, it then searches for the suffix in the remainder of the string.
Algorithm
- Find the index of
*inp. - Extract
prefixandsuffix. - Initialize
searchFromIndex = 0. - Loop:
- Find the index of
prefixinsstarting fromsearchFromIndex. Let it beprefixIndex. - If
prefixis not found (prefixIndex == -1), break the loop. - Calculate the starting position for the suffix search:
suffixSearchStart = prefixIndex + prefix.length(). - Find the index of
suffixinsstarting fromsuffixSearchStart. Let it besuffixIndex. - If
suffixis found (suffixIndex != -1), returntrue. - Update
searchFromIndex = prefixIndex + 1to find the next occurrence ofprefix.
- Find the index of
- If the loop completes, return
false.
Walkthrough
Instead of checking every substring, we can be more direct. We first parse p to get the prefix and suffix. The goal is to find an occurrence of prefix followed by an occurrence of suffix somewhere later in the string s. We can achieve this by iterating through all possible start positions of the prefix. We use s.indexOf(prefix, fromIndex) in a loop to find each occurrence of the prefix. For each prefix found at prefixIndex, we then search for the suffix but only in the part of the string that comes after the prefix ends, i.e., starting from index prefixIndex + prefix.length(). If s.indexOf(suffix, ...) finds a match, we have satisfied the pattern and can return true. If the suffix is not found, we continue to the next occurrence of the prefix by updating our search start position. If we exhaust all occurrences of prefix without finding a subsequent suffix, we return false.
class Solution { public boolean matchPattern(String s, String p) { int starIndex = p.indexOf('*'); String prefix = p.substring(0, starIndex); String suffix = p.substring(starIndex + 1); int fromIndex = 0; while (true) { int prefixIndex = s.indexOf(prefix, fromIndex); if (prefixIndex == -1) { break; // No more occurrences of prefix } int suffixSearchStart = prefixIndex + prefix.length(); int suffixIndex = s.indexOf(suffix, suffixSearchStart); if (suffixIndex != -1) { return true; // Found a valid match } fromIndex = prefixIndex + 1; } return false; }}Complexity
Time
O(N*M) in practice. The outer `while` loop can run up to N times. The `indexOf` method takes O((N-k)*M) where k is the starting index. In total, this can be considered roughly O(N*M) with optimized `indexOf` implementations. In the worst-case with a naive `indexOf`, it could be O(N^2 * M).
Space
O(M), where M is the length of `p`, for storing the `prefix` and `suffix` strings.
Trade-offs
Pros
More efficient than the brute-force approach as it avoids generating and checking every substring.
It's a more targeted search.
Cons
Can be inefficient if the
prefixoccurs very frequently ins, leading to many repeated searches for thesuffix.
This is the most efficient approach. It leverages a key insight: if a match exists, there must be an occurrence of the prefix that appears before an occurrence of the suffix. To check this, we only need to find the first occurrence of the prefix and the last occurrence of the suffix.
Algorithm
- Find the index of
*inp. - Extract
prefixandsuffix. - Find the index of the first occurrence of
prefixins. If not found, returnfalse. - Find the index of the last occurrence of
suffixins. If not found, returnfalse. - Check if the end of the first
prefix(firstPrefixIndex + prefix.length()) is before or at the start of the lastsuffix(lastSuffixIndex). - If
firstPrefixIndex + prefix.length() <= lastSuffixIndex, returntrue. - Otherwise, return
false.
Walkthrough
This optimized approach is based on a simple logical deduction. For a pattern prefix*suffix to match, there must be some instance of prefix at index i and some instance of suffix at index j in s such that i + prefix.length() <= j. To check if such a pair (i, j) exists, we can check the most favorable case: the earliest possible prefix and the latest possible suffix.
We find the index of the very first occurrence of prefix using s.indexOf(prefix). Let this be firstPrefixIndex. Then, we find the index of the very last occurrence of suffix using s.lastIndexOf(suffix). Let this be lastSuffixIndex.
If either prefix or suffix doesn't exist in s, a match is impossible. If both exist, we just need to check if the first prefix ends at or before the last suffix begins. This is true if firstPrefixIndex + prefix.length() <= lastSuffixIndex. If this condition holds, we have found a valid configuration, and we return true. If it doesn't, it means every occurrence of prefix is too late to be followed by any occurrence of suffix, so no match is possible, and we return false.
class Solution { public boolean matchPattern(String s, String p) { int starIndex = p.indexOf('*'); String prefix = p.substring(0, starIndex); String suffix = p.substring(starIndex + 1); int firstPrefixIndex = s.indexOf(prefix); if (firstPrefixIndex == -1) { return false; } int lastSuffixIndex = s.lastIndexOf(suffix); if (lastSuffixIndex == -1) { return false; } return firstPrefixIndex + prefix.length() <= lastSuffixIndex; }}Complexity
Time
O(N * M), where N is the length of `s` and M is the length of `p`. This complexity is dominated by the `indexOf` and `lastIndexOf` calls. With standard library optimizations (like KMP or Boyer-Moore), the complexity is closer to O(N + M).
Space
O(M), where M is the length of `p`, for storing the `prefix` and `suffix` strings.
Trade-offs
Pros
Extremely efficient as it only requires two passes (or one for each search) over the string.
Simple and concise implementation.
Cons
The logic might be slightly less intuitive to come up with compared to a direct iterative search.
Solutions
Solution
class Solution {public boolean hasMatch(String s, String p) { int i = 0; for (String t : p.split("\\*")) { int j = s.indexOf(t, i); if (j == -1) { return false; } i = j + t.length(); } return true; }}class Solution {public: bool hasMatch(string s, string p) { int i = 0; int pos = 0; int start = 0, end; while ((end = p.find("*", start)) != string ::npos) { string t = p.substr(start, end - start); pos = s.find(t, i); if (pos == string ::npos) { return false; } i = pos + t.length(); start = end + 1; } string t = p.substr(start); pos = s.find(t, i); if (pos == string ::npos) { return false; } return true; }};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 TrueVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.