{leetcode}/problems/construct-string-with-minimum-cost/[LeetCode - 3213. 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 operation is
costs[i].
Return the minimum cost to make s equal to target. If it’s not possible, return -1.
Example 1:
<div class="example-block"> Input: <span class="example-io">target = "abcdef", words = ["abdef","abc","d","def","ef"], costs = [100,1,1,10,5]
Output: <span class="example-io">7
Explanation:
The minimum cost can be achieved by performing the following operations:
-
Select index 1 and append
"abc"tosat a cost of 1, resulting ins = "abc". -
Select index 2 and append
"d"tosat a cost of 1, resulting ins = "abcd". -
Select index 4 and append
"ef"tosat a cost of 5, resulting ins = "abcdef".
Example 2:
<div class="example-block"> Input: <span class="example-io">target = "aaaa", words = ["z","zz","zzz"], costs = [1,10,100]
Output: <span class="example-io">-1
Explanation:
It is impossible to make s equal to target, so we return -1.
Constraints:
-
1 ⇐ target.length ⇐ 5 * 104 -
1 ⇐ words.length == costs.length ⇐ 5 * 104 -
1 ⇐ words[i].length ⇐ target.length -
The total sum of
words[i].lengthis less than or equal to5 * 104. -
targetandwords[i]consist only of lowercase English letters. -
1 ⇐ costs[i] ⇐ 104