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

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 an array of strings <code>words</code> and a string <code>target</code>.

A string <code>x</code> is called valid if <code>x</code> is a prefix of any string in <code>words</code>.

Return the minimum number of valid strings that can be concatenated to form <code>target</code>. If it is not possible to form <code>target</code>, return <code>-1</code>.

&nbsp;
Example 1:

<div class="example-block">
Input: words = [&quot;abc&quot;,&quot;aaaaa&quot;,&quot;bcdef&quot;], target = &quot;aabcdabc&quot;

Output: 3

Explanation:

The target string can be formed by concatenating:

<ul>
	<li>Prefix of length 2 of <code>words[1]</code>, i.e. <code>&quot;aa&quot;</code>.</li>
	<li>Prefix of length 3 of <code>words[2]</code>, i.e. <code>&quot;bcd&quot;</code>.</li>
	<li>Prefix of length 3 of <code>words[0]</code>, i.e. <code>&quot;abc&quot;</code>.</li>
</ul>
</div>

Example 2:

<div class="example-block">
Input: words = [&quot;abababab&quot;,&quot;ab&quot;], target = &quot;ababaababa&quot;

Output: 2

Explanation:

The target string can be formed by concatenating:

<ul>
	<li>Prefix of length 5 of <code>words[0]</code>, i.e. <code>&quot;ababa&quot;</code>.</li>
	<li>Prefix of length 5 of <code>words[0]</code>, i.e. <code>&quot;ababa&quot;</code>.</li>
</ul>
</div>

Example 3:

<div class="example-block">
Input: words = [&quot;abcdef&quot;], target = &quot;xyz&quot;

Output: -1
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= words.length &lt;= 100</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 5 * 104</code></li>
	<li>The input is generated such that <code>sum(words[i].length) &lt;= 105</code>.</li>
	<li><code>words[i]</code> consists only of lowercase English letters.</li>
	<li><code>1 &lt;= target.length &lt;= 5 * 104</code></li>
	<li><code>target</code> consists only of lowercase English letters.</li>
</ul>

minValidStrings

Minimum Number of Valid Strings to Form Target II

Minimum Cost to Convert String II

minimum-cost-to-convert-string-ii

转换字符串的最小成本 II

Construct String with Minimum Cost

construct-string-with-minimum-cost

最小代价构造字符串

Segment Tree

Array

String

Binary Search

Dynamic Programming

String Matching

Hash Function

Rolling Hash

给你一个字符串数组 <code>words</code> 和一个字符串 <code>target</code>。

如果字符串 <code>x</code> 是 <code>words</code> 中 任意 字符串的 前缀，则认为 <code>x</code> 是一个 有效 字符串。

现计划通过 连接 有效字符串形成 <code>target</code> ，请你计算并返回需要连接的 最少 字符串数量。如果无法通过这种方式形成 <code>target</code>，则返回 <code>-1</code>。

&nbsp;

示例 1：

<div class="example-block">
输入： words = ["abc","aaaaa","bcdef"], target = "aabcdabc"

输出： 3

解释：

target 字符串可以通过连接以下有效字符串形成：

<ul>
	<li><code>words[1]</code> 的长度为 2 的前缀，即 <code>"aa"</code>。</li>
	<li><code>words[2]</code> 的长度为 3 的前缀，即 <code>"bcd"</code>。</li>
	<li><code>words[0]</code> 的长度为 3 的前缀，即 <code>"abc"</code>。</li>
</ul>
</div>

示例 2：

<div class="example-block">
输入： words = ["abababab","ab"], target = "ababaababa"

输出： 2

解释：

target 字符串可以通过连接以下有效字符串形成：

<ul>
	<li><code>words[0]</code> 的长度为 5 的前缀，即 <code>"ababa"</code>。</li>
	<li><code>words[0]</code> 的长度为 5 的前缀，即 <code>"ababa"</code>。</li>
</ul>
</div>

示例 3：

<div class="example-block">
输入： words = ["abcdef"], target = "xyz"

输出： -1
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= words.length &lt;= 100</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 5 * 104</code></li>
	<li>输入确保 <code>sum(words[i].length) &lt;= 105</code>.</li>
	<li><code>words[i]</code> &nbsp;只包含小写英文字母。</li>
	<li><code>1 &lt;= target.length &lt;= 5 * 104</code></li>
	<li><code>target</code> &nbsp;只包含小写英文字母。</li>
</ul>