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:
words[1], i.e. "aa".words[2], i.e. "bcd".words[0], i.e. "abc".Example 2:
Input: words = ["abababab","ab"], target = "ababaababa"
Output: 2
Explanation:
The target string can be formed by concatenating:
words[0], i.e. "ababa".words[0], i.e. "ababa".Example 3:
Input: words = ["abcdef"], target = "xyz"
Output: -1
Constraints:
1 <= words.length <= 1001 <= words[i].length <= 5 * 104sum(words[i].length) <= 105.words[i] consists only of lowercase English letters.1 <= target.length <= 5 * 104target consists only of lowercase English letters.