3291. Minimum Number of Valid Strings to Form Target I Medium

1/**
2 * [3291] Minimum Number of Valid Strings to Form Target I
3 *
4 * You are given an array of strings words and a string target.
5 * A string x is called valid if x is a <span data-keyword="string-prefix">prefix</span> of any string in words.
6 * Return the minimum number of valid strings that can be concatenated to form target. If it is not possible to form target, return -1.
7 *  
8 * <strong class="example">Example 1:
9 * <div class="example-block">
10 * Input: <span class="example-io">words = ["abc","aaaaa","bcdef"], target = "aabcdabc"</span>
11 * Output: <span class="example-io">3</span>
12 * Explanation:
13 * The target string can be formed by concatenating:
14 * 
15 * 	Prefix of length 2 of words[1], i.e. "aa".
16 * 	Prefix of length 3 of words[2], i.e. "bcd".
17 * 	Prefix of length 3 of words[0], i.e. "abc".
18 * </div>
19 * <strong class="example">Example 2:
20 * <div class="example-block">
21 * Input: <span class="example-io">words = ["abababab","ab"], target = "ababaababa"</span>
22 * Output: <span class="example-io">2</span>
23 * Explanation:
24 * The target string can be formed by concatenating:
25 * 
26 * 	Prefix of length 5 of words[0], i.e. "ababa".
27 * 	Prefix of length 5 of words[0], i.e. "ababa".
28 * </div>
29 * <strong class="example">Example 3:
30 * <div class="example-block">
31 * Input: <span class="example-io">words = ["abcdef"], target = "xyz"</span>
32 * Output: <span class="example-io">-1</span>
33 * </div>
34 *  
35 * Constraints:
36 * 
37 * 	1 <= words.length <= 100
38 * 	1 <= words[i].length <= 5 * 10^3
39 * 	The input is generated such that sum(words[i].length) <= 10^5.
40 * 	words[i] consists only of lowercase English letters.
41 * 	1 <= target.length <= 5 * 10^3
42 * 	target consists only of lowercase English letters.
43 * 
44 */
45pub struct Solution {}
46
47// problem: https://leetcode.com/problems/minimum-number-of-valid-strings-to-form-target-i/
48// discuss: https://leetcode.com/problems/minimum-number-of-valid-strings-to-form-target-i/discuss/?currentPage=1&orderBy=most_votes&query=
49
50// submission codes start here
51
52impl Solution {
53    pub fn min_valid_strings(words: Vec<String>, target: String) -> i32 {
54        0
55    }
56}
57
58// submission codes end
59
60#[cfg(test)]
61mod tests {
62    use super::*;
63
64    #[test]
65    fn test_3291() {
66    }
67}
68