Welcome to Subscribe On Youtube

3455. Shortest Matching Substring

Description

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 '*'.

Solutions

Solution 1

  • class Solution {
    public int shortestMatchingSubstring(String s, String p) {
        int star = p.indexOf('*');
        int star2 = p.indexOf('*', star + 1);
        String a = p.substring(0, star);
        String b = p.substring(star + 1, star2);
        String c = p.substring(star2 + 1);
        int[] A = starts(s, a);
        int[] B = starts(s, b);
        int[] C = starts(s, c);
        int ans = s.length() + 1;
        int j = 0, k = 0;
        for (int i : A) {
            while (j < B.length && B[j] < i + a.length()) {
                ++j;
            }
            if (j == B.length) {
                break;
            }
            while (k < C.length && C[k] < B[j] + b.length()) {
                ++k;
            }
            if (k == C.length) {
                break;
            }
            ans = Math.min(ans, C[k] + c.length() - i);
        }
        return ans > s.length() ? -1 : ans;
    }

    private int[] starts(String s, String pat) {
        int n = s.length();
        if (pat.isEmpty()) {
            int[] res = new int[n + 1];
            for (int i = 0; i <= n; ++i) {
                res[i] = i;
            }
            return res;
        }
        int m = pat.length();
        int[] lps = new int[m];
        for (int i = 1, len = 0; i < m;) {
            if (pat.charAt(i) == pat.charAt(len)) {
                lps[i++] = ++len;
            } else if (len > 0) {
                len = lps[len - 1];
            } else {
                ++i;
            }
        }
        int[] tmp = new int[n];
        int cnt = 0;
        for (int i = 0, j = 0; i < n;) {
            if (s.charAt(i) == pat.charAt(j)) {
                ++i;
                ++j;
                if (j == m) {
                    tmp[cnt++] = i - m;
                    j = lps[j - 1];
                }
            } else if (j > 0) {
                j = lps[j - 1];
            } else {
                ++i;
            }
        }
        int[] res = new int[cnt];
        System.arraycopy(tmp, 0, res, 0, cnt);
        return res;
    }
}


  • class Solution {
public:
    int shortestMatchingSubstring(string s, string p) {
        int star = p.find('*');
        int star2 = p.find('*', star + 1);
        string a = p.substr(0, star);
        string b = p.substr(star + 1, star2 - star - 1);
        string c = p.substr(star2 + 1);
        vector<int> A = starts(s, a), B = starts(s, b), C = starts(s, c);
        int ans = s.size() + 1;
        int j = 0, k = 0;
        for (int i : A) {
            while (j < (int) B.size() && B[j] < i + (int) a.size()) {
                ++j;
            }
            if (j == (int) B.size()) {
                break;
            }
            while (k < (int) C.size() && C[k] < B[j] + (int) b.size()) {
                ++k;
            }
            if (k == (int) C.size()) {
                break;
            }
            ans = min(ans, C[k] + (int) c.size() - i);
        }
        return ans > (int) s.size() ? -1 : ans;
    }

private:
    vector<int> starts(const string& s, const string& pat) {
        int n = s.size();
        if (pat.empty()) {
            vector<int> res(n + 1);
            iota(res.begin(), res.end(), 0);
            return res;
        }
        int m = pat.size();
        vector<int> lps(m);
        for (int i = 1, len = 0; i < m;) {
            if (pat[i] == pat[len]) {
                lps[i++] = ++len;
            } else if (len) {
                len = lps[len - 1];
            } else {
                ++i;
            }
        }
        vector<int> res;
        for (int i = 0, j = 0; i < n;) {
            if (s[i] == pat[j]) {
                ++i;
                ++j;
                if (j == m) {
                    res.push_back(i - m);
                    j = lps[j - 1];
                }
            } else if (j) {
                j = lps[j - 1];
            } else {
                ++i;
            }
        }
        return res;
    }
};


  • class Solution:
    def shortestMatchingSubstring(self, s: str, p: str) -> int:
        def starts(pat: str):
            if not pat:
                return list(range(len(s) + 1))
            m = len(pat)
            lps = [0] * m
            length = 0
            i = 1
            while i < m:
                if pat[i] == pat[length]:
                    length += 1
                    lps[i] = length
                    i += 1
                elif length:
                    length = lps[length - 1]
                else:
                    i += 1
            res = []
            i = j = 0
            n = len(s)
            while i < n:
                if s[i] == pat[j]:
                    i += 1
                    j += 1
                    if j == m:
                        res.append(i - m)
                        j = lps[j - 1]
                elif j:
                    j = lps[j - 1]
                else:
                    i += 1
            return res

        a, b, c = p.split('*')
        A, B, C = starts(a), starts(b), starts(c)
        la, lb, lc = len(a), len(b), len(c)
        ans = len(s) + 1
        j = k = 0
        for i in A:
            while j < len(B) and B[j] < i + la:
                j += 1
            if j == len(B):
                break
            while k < len(C) and C[k] < B[j] + lb:
                k += 1
            if k == len(C):
                break
            ans = min(ans, C[k] + lc - i)
        return -1 if ans > len(s) else ans


  • func shortestMatchingSubstring(s string, p string) int {
	star := 0
	for p[star] != '*' {
		star++
	}
	star2 := star + 1
	for p[star2] != '*' {
		star2++
	}
	a, b, c := p[:star], p[star+1:star2], p[star2+1:]
	A, B, C := matchStarts(s, a), matchStarts(s, b), matchStarts(s, c)
	ans := len(s) + 1
	j, k := 0, 0
	for _, i := range A {
		for j < len(B) && B[j] < i+len(a) {
			j++
		}
		if j == len(B) {
			break
		}
		for k < len(C) && C[k] < B[j]+len(b) {
			k++
		}
		if k == len(C) {
			break
		}
		ans = min(ans, C[k]+len(c)-i)
	}
	if ans > len(s) {
		return -1
	}
	return ans
}

func matchStarts(s, pat string) []int {
	n := len(s)
	if pat == "" {
		res := make([]int, n+1)
		for i := 0; i <= n; i++ {
			res[i] = i
		}
		return res
	}
	m := len(pat)
	lps := make([]int, m)
	for i, length := 1, 0; i < m; {
		if pat[i] == pat[length] {
			length++
			lps[i] = length
			i++
		} else if length > 0 {
			length = lps[length-1]
		} else {
			i++
		}
	}
	res := make([]int, 0)
	for i, j := 0, 0; i < n; {
		if s[i] == pat[j] {
			i++
			j++
			if j == m {
				res = append(res, i-m)
				j = lps[j-1]
			}
		} else if j > 0 {
			j = lps[j-1]
		} else {
			i++
		}
	}
	return res
}

All Problems

All Solutions