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 * 103sum(words[i].length) <= 105.words[i] consists only of lowercase English letters.1 <= target.length <= 5 * 103target consists only of lowercase English letters.This approach uses dynamic programming to solve the problem. We maintain a single dimension DP array where dp[i] tells us the minimum number of valid strings to form the prefix of length i of the target string.
The main idea is to iterate over the target string length and for each position, try each word as a potential prefix. If a substring of the target (starting at some position and of length equal to the length of the word) matches the word (or a prefix), we update the DP table.
This Python solution uses a single dimension DP array initialized with infinity, representing the minimum number of concatenations required to form each prefix of the target string. It iterates over the target string and for each position, checks every word to determine if it can form a valid prefix starting from that position.
JavaScript
Java
Time Complexity: O(t * w * l) where t is the length of the target, w is the number of words and l is the average length of a word.
Space Complexity: O(t) for the DP array.
This backtracking approach leverages DFS to try to build the target string step by step using valid prefixes. It explores each possibility and takes note of the minimum number of segments needed. This method is less efficient for large inputs compared to DP but is easier to conceptualize.
This C solution uses recursive backtracking combined with memoization. The helper function tries every word as a prefix starting from the given index in the target string and recursively calls itself to check the remaining string.
C++
Time Complexity: Exponential in theory, reduced to O(t * w * l) due to memoization.
Space Complexity: O(t) for memoization storage.
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(t * w * l) where Space Complexity: O(t) for the DP array. |
| Recursive Backtracking Approach | Time Complexity: Exponential in theory, reduced to O(t * w * l) due to memoization. Space Complexity: O(t) for memoization storage. |
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 I with our built-in code editor and test cases.
Practice on FleetCode