3455. Shortest Matching Substring Hard

1/**
2 * [3455] Shortest Matching Substring
3 *
4 * You are given a string s and a pattern string p, where p contains exactly two '*' characters.
5 * The '*' in p matches any sequence of zero or more characters.
6 * Return the length of the shortest <span data-keyword="substring">substring</span> in s that matches p. If there is no such substring, return -1.
7 * Note: The empty substring is considered valid.
8 *  
9 * <strong class="example">Example 1:
10 * <div class="example-block">
11 * Input: <span class="example-io">s = "abaacbaecebce", p = "ba*c*ce"</span>
12 * Output: <span class="example-io">8</span>
13 * Explanation:
14 * The shortest matching substring of p in s is "<u>ba</u>e<u>c</u>eb<u>ce</u>".
15 * </div>
16 * <strong class="example">Example 2:
17 * <div class="example-block">
18 * Input: <span class="example-io">s = "baccbaadbc", p = "cc*baa*adb"</span>
19 * Output: <span class="example-io">-1</span>
20 * Explanation:
21 * There is no matching substring in s.
22 * </div>
23 * <strong class="example">Example 3:
24 * <div class="example-block">
25 * Input: <span class="example-io">s = "a", p = "**"</span>
26 * Output: <span class="example-io">0</span>
27 * Explanation:
28 * The empty substring is the shortest matching substring.
29 * </div>
30 * <strong class="example">Example 4:
31 * <div class="example-block">
32 * Input: <span class="example-io">s = "madlogic", p = "*adlogi*"</span>
33 * Output: <span class="example-io">6</span>
34 * Explanation:
35 * The shortest matching substring of p in s is "<u>adlogi</u>".
36 * </div>
37 *  
38 * Constraints:
39 * 
40 * 	1 <= s.length <= 10^5
41 * 	2 <= p.length <= 10^5
42 * 	s contains only lowercase English letters.
43 * 	p contains only lowercase English letters and exactly two '*'.
44 * 
45 */
46pub struct Solution {}
47
48// problem: https://leetcode.com/problems/shortest-matching-substring/
49// discuss: https://leetcode.com/problems/shortest-matching-substring/discuss/?currentPage=1&orderBy=most_votes&query=
50
51// submission codes start here
52
53impl Solution {
54    pub fn shortest_matching_substring(s: String, p: String) -> i32 {
55        0
56    }
57}
58
59// submission codes end
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64
65    #[test]
66    fn test_3455() {
67    }
68}
69