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.This approach involves using dynamic programming to determine the minimum number of valid string prefixes needed to form the target string. We define a DP array where each state represents the minimum number of prefixes required to form a prefix of the target of a given length.
We initialize a DP array to store the minimum number of prefixes required for each prefix length of the target. For each end position of a substring of the target, we check all possible starting positions. If the substring is in the set of words, we update the DP table.
JavaScript
C++
Time Complexity: O(n2) where n is the length of the target string.
Space Complexity: O(n) for the DP array.
This approach leverages a backtracking strategy to identify valid prefixes greedily, trying to cut the target string into chunks from the longest valid prefix available and backtracking when necessary.
This solution uses a recursive function with backtracking to explore all possible ways to split the target into valid prefixes. It terminates on the successful attempt that minimizes the count.
JavaScript
Time Complexity: Exponential in the worst case, depending on branching factors.
Space Complexity: O(m) where m is the recursion stack depth.
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n2) where n is the length of the target string. |
| Greedy Approach with Backtracking | Time Complexity: Exponential in the worst case, depending on branching factors. |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,306 views views
Watch 9 more video solutions →Practice Minimum Number of Valid Strings to Form Target II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor