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.
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; }}Video 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.