2977. Minimum Cost to Convert String II Hard

1/**
2 * [2977] Minimum Cost to Convert String II
3 *
4 * You are given two 0-indexed strings source and target, both of length n and consisting of lowercase English characters. You are also given two 0-indexed string arrays original and changed, and an integer array cost, where cost[i] represents the cost of converting the string original[i] to the string changed[i].
5 * You start with the string source. In one operation, you can pick a substring x from the string, and change it to y at a cost of z if there exists any index j such that cost[j] == z, original[j] == x, and changed[j] == y. You are allowed to do any number of operations, but any pair of operations must satisfy either of these two conditions:
6 * 
7 * 	The substrings picked in the operations are source[a..b] and source[c..d] with either b < c or d < a. In other words, the indices picked in both operations are disjoint.
8 * 	The substrings picked in the operations are source[a..b] and source[c..d] with a == c and b == d. In other words, the indices picked in both operations are identical.
9 * 
10 * Return the minimum cost to convert the string source to the string target using any number of operations. If it is impossible to convert source to target, return -1.
11 * Note that there may exist indices i, j such that original[j] == original[i] and changed[j] == changed[i].
12 *  
13 * <strong class="example">Example 1:
14 * 
15 * Input: source = "abcd", target = "acbe", original = ["a","b","c","c","e","d"], changed = ["b","c","b","e","b","e"], cost = [2,5,5,1,2,20]
16 * Output: 28
17 * Explanation: To convert "abcd" to "acbe", do the following operations:
18 * - Change substring source[1..1] from "b" to "c" at a cost of 5.
19 * - Change substring source[2..2] from "c" to "e" at a cost of 1.
20 * - Change substring source[2..2] from "e" to "b" at a cost of 2.
21 * - Change substring source[3..3] from "d" to "e" at a cost of 20.
22 * The total cost incurred is 5 + 1 + 2 + 20 = 28. 
23 * It can be shown that this is the minimum possible cost.
24 * 
25 * <strong class="example">Example 2:
26 * 
27 * Input: source = "abcdefgh", target = "acdeeghh", original = ["bcd","fgh","thh"], changed = ["cde","thh","ghh"], cost = [1,3,5]
28 * Output: 9
29 * Explanation: To convert "abcdefgh" to "acdeeghh", do the following operations:
30 * - Change substring source[1..3] from "bcd" to "cde" at a cost of 1.
31 * - Change substring source[5..7] from "fgh" to "thh" at a cost of 3. We can do this operation because indices [5,7] are disjoint with indices picked in the first operation.
32 * - Change substring source[5..7] from "thh" to "ghh" at a cost of 5. We can do this operation because indices [5,7] are disjoint with indices picked in the first operation, and identical with indices picked in the second operation.
33 * The total cost incurred is 1 + 3 + 5 = 9.
34 * It can be shown that this is the minimum possible cost.
35 * 
36 * <strong class="example">Example 3:
37 * 
38 * Input: source = "abcdefgh", target = "addddddd", original = ["bcd","defgh"], changed = ["ddd","ddddd"], cost = [100,1578]
39 * Output: -1
40 * Explanation: It is impossible to convert "abcdefgh" to "addddddd".
41 * If you select substring source[1..3] as the first operation to change "abcdefgh" to "adddefgh", you cannot select substring source[3..7] as the second operation because it has a common index, 3, with the first operation.
42 * If you select substring source[3..7] as the first operation to change "abcdefgh" to "abcddddd", you cannot select substring source[1..3] as the second operation because it has a common index, 3, with the first operation.
43 * 
44 *  
45 * Constraints:
46 * 
47 * 	1 <= source.length == target.length <= 1000
48 * 	source, target consist only of lowercase English characters.
49 * 	1 <= cost.length == original.length == changed.length <= 100
50 * 	1 <= original[i].length == changed[i].length <= source.length
51 * 	original[i], changed[i] consist only of lowercase English characters.
52 * 	original[i] != changed[i]
53 * 	1 <= cost[i] <= 10^6
54 * 
55 */
56pub struct Solution {}
57
58// problem: https://leetcode.com/problems/minimum-cost-to-convert-string-ii/
59// discuss: https://leetcode.com/problems/minimum-cost-to-convert-string-ii/discuss/?currentPage=1&orderBy=most_votes&query=
60
61// submission codes start here
62
63impl Solution {
64    pub fn minimum_cost(source: String, target: String, original: Vec<String>, changed: Vec<String>, cost: Vec<i32>) -> i64 {
65        
66    }
67}
68
69// submission codes end
70
71#[cfg(test)]
72mod tests {
73    use super::*;
74
75    #[test]
76    fn test_2977() {
77    }
78}
79