Construct String with Minimum Cost
You are given a string target, an array of strings words, and an integer array costs, both arrays of the same length.
Imagine an empty string s.
You can perform the following operation any number of times, including zero:
- Choose an index
iin the range[0, words.length - 1]. - Append
words[i]tos. - The cost of the operation is
costs[i].
Return the minimum cost to make s equal to target. If it is not possible, return -1.
Example 1
Input
target = "abcdef", words = ["abdef","abc","d","def","ef"], costs = [100,1,1,10,5]Output
7The minimum cost is achieved by appending
"abc", then "d", then "ef", for a total cost of 1 + 1 + 5 = 7.Example 2
Input
target = "aaaa", words = ["z","zz","zzz"], costs = [1,10,100]Output
-1It is impossible to make
s equal to target, so the result is -1.Constraints
- 1 <= target.length <= 5 * 10^4
- 1 <= words.length == costs.length <= 5 * 10^4
- 1 <= words[i].length <= target.length
- The total sum of words[i].length is less than or equal to 5 * 10^4.
- target and words[i] consist only of lowercase English letters.
- 1 <= costs[i] <= 10^4