mirror of
https://gitee.com/coder-xiaomo/leetcode-problemset
synced 2025-01-10 18:48:13 +08:00
57 lines
2.6 KiB
HTML
57 lines
2.6 KiB
HTML
|
<p>You are given a string <code>target</code>, an array of strings <code>words</code>, and an integer array <code>costs</code>, both arrays of the same length.</p>
|
||
|
|
|
||
|
|
<p>Imagine an empty string <code>s</code>.</p>
|
||
|
|
|
||
|
|
<p>You can perform the following operation any number of times (including <strong>zero</strong>):</p>
|
||
|
|
|
||
|
|
<ul>
|
||
|
|
<li>Choose an index <code>i</code> in the range <code>[0, words.length - 1]</code>.</li>
|
||
|
|
<li>Append <code>words[i]</code> to <code>s</code>.</li>
|
||
|
|
<li>The cost of operation is <code>costs[i]</code>.</li>
|
||
|
|
</ul>
|
||
|
|
|
||
|
|
<p>Return the <strong>minimum</strong> cost to make <code>s</code> equal to <code>target</code>. If it's not possible, return <code>-1</code>.</p>
|
||
|
|
|
||
|
|
<p> </p>
|
||
|
|
<p><strong class="example">Example 1:</strong></p>
|
||
|
|
|
||
|
|
<div class="example-block">
|
||
|
|
<p><strong>Input:</strong> <span class="example-io">target = "abcdef", words = ["abdef","abc","d","def","ef"], costs = [100,1,1,10,5]</span></p>
|
||
|
|
|
||
|
|
<p><strong>Output:</strong> <span class="example-io">7</span></p>
|
||
|
|
|
||
|
|
<p><strong>Explanation:</strong></p>
|
||
|
|
|
||
|
|
<p>The minimum cost can be achieved by performing the following operations:</p>
|
||
|
|
|
||
|
|
<ul>
|
||
|
|
<li>Select index 1 and append <code>"abc"</code> to <code>s</code> at a cost of 1, resulting in <code>s = "abc"</code>.</li>
|
||
|
|
<li>Select index 2 and append <code>"d"</code> to <code>s</code> at a cost of 1, resulting in <code>s = "abcd"</code>.</li>
|
||
|
|
<li>Select index 4 and append <code>"ef"</code> to <code>s</code> at a cost of 5, resulting in <code>s = "abcdef"</code>.</li>
|
||
|
|
</ul>
|
||
|
|
</div>
|
||
|
|
|
||
|
|
<p><strong class="example">Example 2:</strong></p>
|
||
|
|
|
||
|
|
<div class="example-block">
|
||
|
|
<p><strong>Input:</strong> <span class="example-io">target = "aaaa", words = ["z","zz","zzz"], costs = [1,10,100]</span></p>
|
||
|
|
|
||
|
|
<p><strong>Output:</strong> <span class="example-io">-1</span></p>
|
||
|
|
|
||
|
|
<p><strong>Explanation:</strong></p>
|
||
|
|
|
||
|
|
<p>It is impossible to make <code>s</code> equal to <code>target</code>, so we return -1.</p>
|
||
|
|
</div>
|
||
|
|
|
||
|
|
<p> </p>
|
||
|
|
<p><strong>Constraints:</strong></p>
|
||
|
|
|
||
|
|
<ul>
|
||
|
|
<li><code>1 <= target.length <= 5 * 10<sup>4</sup></code></li>
|
||
|
|
<li><code>1 <= words.length == costs.length <= 5 * 10<sup>4</sup></code></li>
|
||
|
|
<li><code>1 <= words[i].length <= target.length</code></li>
|
||
|
|
<li>The total sum of <code>words[i].length</code> is less than or equal to <code>5 * 10<sup>4</sup></code>.</li>
|
||
|
|
<li><code>target</code> and <code>words[i]</code> consist only of lowercase English letters.</li>
|
||
|
|
<li><code>1 <= costs[i] <= 10<sup>4</sup></code></li>
|
||
|
|
</ul>
|