3213. Construct String with Minimum Cost Hard

1/**
2 * [3213] Construct String with Minimum Cost
3 *
4 * You are given a string target, an array of strings words, and an integer array costs, both arrays of the same length.
5 * Imagine an empty string s.
6 * You can perform the following operation any number of times (including zero):
7 * 
8 * 	Choose an index i in the range [0, words.length - 1].
9 * 	Append words[i] to s.
10 * 	The cost of operation is costs[i].
11 * 
12 * Return the minimum cost to make s equal to target. If it's not possible, return -1.
13 *  
14 * <strong class="example">Example 1:
15 * <div class="example-block">
16 * Input: <span class="example-io">target = "abcdef", words = ["abdef","abc","d","def","ef"], costs = [100,1,1,10,5]</span>
17 * Output: <span class="example-io">7</span>
18 * Explanation:
19 * The minimum cost can be achieved by performing the following operations:
20 * 
21 * 	Select index 1 and append "abc" to s at a cost of 1, resulting in s = "abc".
22 * 	Select index 2 and append "d" to s at a cost of 1, resulting in s = "abcd".
23 * 	Select index 4 and append "ef" to s at a cost of 5, resulting in s = "abcdef".
24 * </div>
25 * <strong class="example">Example 2:
26 * <div class="example-block">
27 * Input: <span class="example-io">target = "aaaa", words = ["z","zz","zzz"], costs = [1,10,100]</span>
28 * Output: <span class="example-io">-1</span>
29 * Explanation:
30 * It is impossible to make s equal to target, so we return -1.
31 * </div>
32 *  
33 * Constraints:
34 * 
35 * 	1 <= target.length <= 5 * 10^4
36 * 	1 <= words.length == costs.length <= 5 * 10^4
37 * 	1 <= words[i].length <= target.length
38 * 	The total sum of words[i].length is less than or equal to 5 * 10^4.
39 * 	target and words[i] consist only of lowercase English letters.
40 * 	1 <= costs[i] <= 10^4
41 * 
42 */
43pub struct Solution {}
44
45// problem: https://leetcode.com/problems/construct-string-with-minimum-cost/
46// discuss: https://leetcode.com/problems/construct-string-with-minimum-cost/discuss/?currentPage=1&orderBy=most_votes&query=
47
48// submission codes start here
49
50impl Solution {
51    pub fn minimum_cost(target: String, words: Vec<String>, costs: Vec<i32>) -> i32 {
52        0
53    }
54}
55
56// submission codes end
57
58#[cfg(test)]
59mod tests {
60    use super::*;
61
62    #[test]
63    fn test_3213() {
64    }
65}
66