construct-string-with-minimum-cost

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

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.

Imagine an empty string <code>s</code>.

You can perform the following operation any number of times (including zero):

<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>

Return the minimum cost to make <code>s</code> equal to <code>target</code>. If it&#39;s not possible, return <code>-1</code>.

&nbsp;
Example 1:

<div class="example-block">
Input: target = &quot;abcdef&quot;, words = [&quot;abdef&quot;,&quot;abc&quot;,&quot;d&quot;,&quot;def&quot;,&quot;ef&quot;], costs = [100,1,1,10,5]

Output: 7

Explanation:

The minimum cost can be achieved by performing the following operations:

<ul>
	<li>Select index 1 and append <code>&quot;abc&quot;</code> to <code>s</code> at a cost of 1, resulting in <code>s = &quot;abc&quot;</code>.</li>
	<li>Select index 2 and append <code>&quot;d&quot;</code> to <code>s</code> at a cost of 1, resulting in <code>s = &quot;abcd&quot;</code>.</li>
	<li>Select index 4 and append <code>&quot;ef&quot;</code> to <code>s</code> at a cost of 5, resulting in <code>s = &quot;abcdef&quot;</code>.</li>
</ul>
</div>

Example 2:

<div class="example-block">
Input: target = &quot;aaaa&quot;, words = [&quot;z&quot;,&quot;zz&quot;,&quot;zzz&quot;], costs = [1,10,100]

Output: -1

Explanation:

It is impossible to make <code>s</code> equal to <code>target</code>, so we return -1.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= target.length &lt;= 5 * 104</code></li>
	<li><code>1 &lt;= words.length == costs.length &lt;= 5 * 104</code></li>
	<li><code>1 &lt;= words[i].length &lt;= target.length</code></li>
	<li>The total sum of <code>words[i].length</code> is less than or equal to <code>5 * 104</code>.</li>
	<li><code>target</code> and <code>words[i]</code> consist only of lowercase English letters.</li>
	<li><code>1 &lt;= costs[i] &lt;= 104</code></li>
</ul>

minimumCost

Construct String with Minimum Cost

Minimum Number of Valid Strings to Form Target II

minimum-number-of-valid-strings-to-form-target-ii

形成目标字符串需要的最少字符串数 II

Minimum Number of Valid Strings to Form Target I

minimum-number-of-valid-strings-to-form-target-i

形成目标字符串需要的最少字符串数 I

Array

String

Dynamic Programming

Suffix Array

给你一个字符串 <code>target</code>、一个字符串数组 <code>words</code> 以及一个整数数组 <code>costs</code>，这两个数组长度相同。

设想一个空字符串 <code>s</code>。

你可以执行以下操作任意次数（包括&nbsp;零&nbsp;次）：

<ul>
	<li>选择一个在范围&nbsp; <code>[0, words.length - 1]</code> 的索引 <code>i</code>。</li>
	<li>将 <code>words[i]</code> 追加到 <code>s</code>。</li>
	<li>该操作的成本是 <code>costs[i]</code>。</li>
</ul>

返回使 <code>s</code> 等于 <code>target</code> 的 最小 成本。如果不可能，返回 <code>-1</code>。

&nbsp;

示例 1：

<div class="example-block">
输入： target = "abcdef", words = ["abdef","abc","d","def","ef"], costs = [100,1,1,10,5]

输出： 7

解释：

<ul>
	<li>选择索引 1 并以成本 1 将 <code>"abc"</code> 追加到 <code>s</code>，得到 <code>s = "abc"</code>。</li>
	<li>选择索引 2 并以成本 1 将 <code>"d"</code> 追加到 <code>s</code>，得到 <code>s = "abcd"</code>。</li>
	<li>选择索引 4 并以成本 5 将 <code>"ef"</code> 追加到 <code>s</code>，得到 <code>s = "abcdef"</code>。</li>
</ul>
</div>

示例 2：

<div class="example-block">
输入： target = "aaaa", words = ["z","zz","zzz"], costs = [1,10,100]

输出： -1

解释：

无法使 <code>s</code> 等于 <code>target</code>，因此返回 -1。
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= target.length &lt;= 5 * 104</code></li>
	<li><code>1 &lt;= words.length == costs.length &lt;= 5 * 104</code></li>
	<li><code>1 &lt;= words[i].length &lt;= target.length</code></li>
	<li>所有 <code>words[i].length</code> 的总和小于或等于 <code>5 * 104</code></li>
	<li><code>target</code> 和 <code>words[i]</code> 仅由小写英文字母组成。</li>
	<li><code>1 &lt;= costs[i] &lt;= 104</code></li>
</ul>