817. Construct String with Minimum Cost (Easy)
Given a string target, an array of strings words, and an integer array costs of the same length. You start with an empty string s and can perform the following operation any number of times to construct target with minimal cost:
- Choose an index i in the range [0, words.length - 1].
- Append words[i] to s.
- The cost of the operation is costs[i].
The goal is to construct target using the given words while minimizing the total cost. If it is not possible to construct target, return -1.
Example 1:
Input: target = "qwerty", words = ["qwrty","qwe","r","rty","ty"], costs = [100,1,1,10,5]Â Â
Output: 7Â Â
Explanation:
Append "qwe" (cost = 1) → s = "qwe"
Append "r" (cost = 1) → s = "qwer"
Append "ty" (cost = 5) → s = "qwerty"
Total cost = 1 + 1 + 5 = 7
Example 2:
Input: target = "mmmm", words = ["s","ss","sss"], costs = [1,10,100]Â Â
Output: -1Â Â
Explanation:
None of the words contain "m", so it's impossible to construct "mmmm".
Return -1.
Now Your Turn!
Pick the correct output for the given inputInput: target = "catcat",words = ["cat","ca","t","at"], costs = [5,3,1,2]Â Â
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- 1 <= target.length <= 2000
- 1 <= words.length == costs.length <= 50
- 1 <= words[i].length <= target.length
- target and words[i] contain only lowercase English letters
- 1 <= costs[i] <= 105