mediumArrayBinary SearchDynamic ProgrammingHash FunctionRolling HashSegment TreeStringString MatchingTrie 0 views
Minimum Number of Valid Strings to Form Target I
You are given an array of strings words and a string target.
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:
Example 2
Input: words = ["abababab","ab"], target = "ababaababa"
Output: 2
Explanation: The target string can be formed by concatenating:
Example 3
Input: words = ["abcdef"], target = "xyz"
Output: -1
Constraints
- 1 <= words.length <= 100
- 1 <= words[i].length <= 5 * 10^3
- The input is generated such that sum(words[i].length) <= 10^5.
- words[i] consists only of lowercase English letters.
- 1 <= target.length <= 5 * 10^3
- target consists only of lowercase English letters.
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.