README_EN.md

comments	difficulty	edit_url	rating	source	tags
true	Hard	https://github.com/doocs/leetcode/edit/main/solution/3200-3299/3292.Minimum%20Number%20of%20Valid%20Strings%20to%20Form%20Target%20II/README_EN.md	2661	Weekly Contest 415 Q4	Segment Tree Array String Binary Search Dynamic Programming String Matching Hash Function Rolling Hash

3292. Minimum Number of Valid Strings to Form Target II

中文文档

Description

You are given an array of strings words and a string target.

A string x is called valid if x is a prefix of any string in words.

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

 

Example 1:

Input: words = ["abc","aaaaa","bcdef"], target = "aabcdabc"

Output: 3

Explanation:

The target string can be formed by concatenating:

• Prefix of length 2 of words[1], i.e. "aa".
• Prefix of length 3 of words[2], i.e. "bcd".
• Prefix of length 3 of words[0], i.e. "abc".

Example 2:

Input: words = ["abababab","ab"], target = "ababaababa"

Output: 2

Explanation:

The target string can be formed by concatenating:

• Prefix of length 5 of words[0], i.e. "ababa".
• Prefix of length 5 of words[0], i.e. "ababa".

Example 3:

Input: words = ["abcdef"], target = "xyz"

Output: -1

 

Constraints:

• 1 <= words.length <= 100
• 1 <= words[i].length <= 5 * 104
• The input is generated such that sum(words[i].length) <= 105.
• words[i] consists only of lowercase English letters.
• 1 <= target.length <= 5 * 104
• target consists only of lowercase English letters.

Solutions

Solution 1

Python3

Java

C++

Go