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.
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):
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:
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 <= 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
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.