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):
i in the range [0, words.length - 1].words[i] to s.costs[i].Return the minimum cost to make s equal to target. If it's not possible, return -1.
Example 1:
Input: target = "abcdef", words = ["abdef","abc","d","def","ef"], costs = [100,1,1,10,5]
Output: 7
Explanation:
The minimum cost can be achieved by performing the following operations:
"abc" to s at a cost of 1, resulting in s = "abc"."d" to s at a cost of 1, resulting in s = "abcd"."ef" to s at a cost of 5, resulting in s = "abcdef".Example 2:
Input: target = "aaaa", words = ["z","zz","zzz"], costs = [1,10,100]
Output: -1
Explanation:
It is impossible to make s equal to target, so we return -1.
Constraints:
1 <= target.length <= 20001 <= words.length == costs.length <= 501 <= words[i].length <= target.lengthtarget and words[i] consist only of lowercase English letters.1 <= costs[i] <= 105Loading editor...
"abcdef" ["abdef","abc","d","def","ef"] [100,1,1,10,5]