3455. Shortest Matching Substring LeetCode Solution
In this guide, you will get 3455. Shortest Matching Substring LeetCode Solution with the best time and space complexity. The solution to Shortest Matching Substring problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Shortest Matching Substring solution in C++
- Shortest Matching Substring solution in Java
- Shortest Matching Substring solution in Python
- Additional Resources
Problem Statement of Shortest Matching Substring
You are given a string s and a pattern string p, where p contains exactly two ‘*’ characters.
The ‘*’ in p matches any sequence of zero or more characters.
Return the length of the shortest substring in s that matches p. If there is no such substring, return -1.
Note: The empty substring is considered valid.
Example 1:
Input: s = “abaacbaecebce”, p = “ba*c*ce”
Output: 8
Explanation:
The shortest matching substring of p in s is “baecebce”.
Example 2:
Input: s = “baccbaadbc”, p = “cc*baa*adb”
Output: -1
Explanation:
There is no matching substring in s.
Example 3:
Input: s = “a”, p = “**”
Output: 0
Explanation:
The empty substring is the shortest matching substring.
Example 4:
Input: s = “madlogic”, p = “*adlogi*”
Output: 6
Explanation:
The shortest matching substring of p in s is “adlogi”.
Constraints:
1 <= s.length <= 105
2 <= p.length <= 105
s contains only lowercase English letters.
p contains only lowercase English letters and exactly two '*'.
Complexity Analysis
- Time Complexity: O(|\texttt{s}| + |\texttt{p}|)
- Space Complexity: O(|\texttt{s}| + |\texttt{p}|)
3455. Shortest Matching Substring LeetCode Solution in C++
class Solution {
public:
int shortestMatchingSubstring(string s, string p) {
const auto [a, b, c] = split(p);
const int ns = s.length();
const int na = a.length();
const int nb = b.length();
const int nc = c.length();
const vector<int> lpsA = getLPS(a + '#' + s);
const vector<int> lpsB = getLPS(b + '#' + s);
const vector<int> lpsC = getLPS(c + '#' + s);
int ans = INT_MAX;
for (int i = 0, j = 0, k = 0; i + nb + nc < ns; ++i) {
while (i < ns && lpsA[na + 1 + i] != na)
++i;
while (j < ns && (j < i + nb || lpsB[nb + 1 + j] != nb))
++j;
while (k < ns && (k < j + nc || lpsC[nc + 1 + k] != nc))
++k;
if (k == ns)
break;
ans = min(ans, k - i + na);
}
return ans == INT_MAX ? -1 : ans;
}
private:
// Returns the lps array, where lps[i] is the length of the longest prefix of
// pattern[0..i] which is also a suffix of this substring.
vector<int> getLPS(const string& pattern) {
vector<int> lps(pattern.length());
for (int i = 1, j = 0; i < pattern.length(); ++i) {
while (j > 0 && pattern[j] != pattern[i])
j = lps[j - 1];
if (pattern[i] == pattern[j])
lps[i] = ++j;
}
return lps;
}
tuple<string, string, string> split(const string& p) {
const int i = p.find('*');
const int j = p.find('*', i + 1);
return {p.substr(0, i), p.substr(i + 1, j - i - 1), p.substr(j + 1)};
}
};
/* code provided by PROGIEZ */3455. Shortest Matching Substring LeetCode Solution in Java
class Solution {
public int shortestMatchingSubstring(String s, String p) {
final String[] parts = split(p);
final String a = parts[0];
final String b = parts[1];
final String c = parts[2];
final int ns = s.length();
final int na = a.length();
final int nb = b.length();
final int nc = c.length();
int[] lpsA = getLPS(a + "#" + s);
int[] lpsB = getLPS(b + "#" + s);
int[] lpsC = getLPS(c + "#" + s);
int ans = Integer.MAX_VALUE;
for (int i = 0, j = 0, k = 0; i + nb + nc < ns; ++i) {
while (i < ns && lpsA[na + 1 + i] != na)
++i;
while (j < ns && (j < i + nb || lpsB[nb + 1 + j] != nb))
++j;
while (k < ns && (k < j + nc || lpsC[nc + 1 + k] != nc))
++k;
if (k == ns)
break;
ans = Math.min(ans, k - i + na);
}
return ans == Integer.MAX_VALUE ? -1 : ans;
}
// Returns the lps array, where lps[i] is the length of the longest prefix of
// pattern[0..i] which is also a suffix of this substring.
private int[] getLPS(String pattern) {
int[] lps = new int[pattern.length()];
for (int i = 1, j = 0; i < pattern.length(); ++i) {
while (j > 0 && pattern.charAt(j) != pattern.charAt(i))
j = lps[j - 1];
if (pattern.charAt(i) == pattern.charAt(j))
lps[i] = ++j;
}
return lps;
}
private String[] split(final String p) {
final int i = p.indexOf('*');
final int j = p.indexOf('*', i + 1);
return new String[] {p.substring(0, i), p.substring(i + 1, j), p.substring(j + 1)};
}
}
// code provided by PROGIEZ3455. Shortest Matching Substring LeetCode Solution in Python
class Solution:
def shortestMatchingSubstring(self, s: str, p: str) -> int:
n = len(s)
a, b, c = p.split('*')
lpsA = self._getLPS(a + '#' + s)[len(a) + 1:]
lpsB = self._getLPS(b + '#' + s)[len(b) + 1:]
lpsC = self._getLPS(c + '#' + s)[len(c) + 1:]
ans = math.inf
i = 0 # lpsA's index
j = 0 # lpsB's index
k = 0 # lpsC's index
while i + len(b) + len(c) < n:
while i < n and lpsA[i] != len(a):
i += 1
while j < n and (j < i + len(b) or lpsB[j] != len(b)):
j += 1
while k < n and (k < j + len(c) or lpsC[k] != len(c)):
k += 1
if k == n:
break
ans = min(ans, k - i + len(a))
i += 1
return -1 if ans == math.inf else ans
def _getLPS(self, pattern: str) -> list[int]:
"""
Returns the lps array, where lps[i] is the length of the longest prefix of
pattern[0..i] which is also a suffix of this substring.
"""
lps = [0] * len(pattern)
j = 0
for i in range(1, len(pattern)):
while j > 0 and pattern[j] != pattern[i]:
j = lps[j - 1]
if pattern[i] == pattern[j]:
lps[i] = j + 1
j += 1
return lps
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.