Substring Matching Pattern — Solution in Python, Java & C++
Substring Matching Pattern solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Substring Matching Pattern is an easy coding problem on strings and string matching, asked in Google interviews.
- Difficulty: Easy
- Topics: Strings, String Matching
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string s and a pattern p that contains exactly one '*'.
The '*' may be replaced by any sequence of zero or more characters. Return true if p can be turned this way into a substring of s, and false otherwise. (A substring is a contiguous, possibly empty, run of characters.)
Example 1
Input: s = "leetcode", p = "ee*e"
Output: true
Explanation: Replacing '*' with "tcod" gives "eetcode", a substring of s.
Example 2
Input: s = "car", p = "c*v"
Output: false
Explanation: There is no 'v' in s at all.
Example 3
Input: s = "luck", p = "u*"
Output: true
Explanation: "u", "uc" and "uck" all match.
Constraints
1 <= s.length <= 501 <= p.length <= 50s contains only lowercase English lettersp contains only lowercase English letters and exactly one '*'
Hints for Substring Matching Pattern
Hint 1
Split
pat the star into a prefixaand a suffixb. You need an occurrence ofafollowed, later and without overlap, by an occurrence ofb.Hint 2
Which occurrence of
agivesbthe most room?Hint 3
Take the leftmost occurrence of
a, then search forbstarting right after it. Emptyaorbalways match.
How to solve Substring Matching Pattern
A match is a, then anything, then b, inside s. Choosing the earliest occurrence of a leaves the longest tail of s in which to find b, so a single greedy pair of searches decides it.
Approach
- Let
a = p[0 .. star)andb = p[star + 1 ..]. - Find the first index
iwhereaoccurs ins; if there is none, returnfalse. - Return whether
boccurs insat some index>= i + a.length.
Why it works
If any match exists, with a at i' and b at j >= i' + |a|, then the leftmost occurrence i <= i' satisfies j >= i + |a| too, so the greedy search finds b as well. Conversely anything it finds is a valid match.
Complexity
- Time —
O(n * m) - Space —
O(1)
Pitfalls
aandbmust not overlap: in s = "ab", p = "ab*b" is false.- An empty side matches anywhere — some library calls (Swift's
range(of:), PHP 7'sstrpos) mishandle an empty needle, so test it explicitly.
Reference solution
Python
def hasMatch(s: str, p: str) -> bool:
star = p.index("*")
a, b = p[:star], p[star + 1:]
i = s.find(a)
if i < 0:
return False
return s.find(b, i + len(a)) >= 0Java
public static boolean hasMatch(String s, String p) {
int star = p.indexOf('*');
String a = p.substring(0, star), b = p.substring(star + 1);
int i = s.indexOf(a);
if (i < 0) return false;
return s.indexOf(b, i + a.length()) >= 0;
}C++
bool hasMatch(string s, string p) {
size_t star = p.find('*');
string a = p.substr(0, star), b = p.substr(star + 1);
size_t i = s.find(a);
if (i == string::npos) return false;
return s.find(b, i + a.size()) != string::npos;
}JavaScript
var hasMatch = function(s, p) {
var star = p.indexOf("*");
var a = p.substring(0, star), b = p.substring(star + 1);
var i = s.indexOf(a);
if (i < 0) return false;
return s.indexOf(b, i + a.length) >= 0;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings