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.Problem Overview: You are given a list of valid strings and a target. The goal is to build the target by concatenating prefixes of these valid strings. Each chosen segment must match a prefix of some string in the list. Return the minimum number of segments required to construct the full target, or -1 if it cannot be formed.
Approach 1: Recursive Backtracking (Exponential Time, O(2^n) time, O(n) space)
This approach tries every possible way to build the target starting from index 0. At each position, iterate through all valid strings and check whether any prefix of that string matches the current portion of the target. If it matches, recursively continue building the target from the next index. Track the minimum number of segments used. Because the recursion explores many overlapping subproblems, the time complexity grows exponentially in the worst case. Space complexity is O(n) from the recursion stack. This approach demonstrates the core idea but becomes slow for large inputs.
Approach 2: Dynamic Programming with Prefix Matching (O(n * L) time, O(n) space)
A more efficient strategy uses dynamic programming. Define dp[i] as the minimum number of valid segments needed to construct the prefix target[0:i]. Initialize dp[0] = 0 and iterate through the target string. For each index i, attempt to match prefixes of all valid strings starting at that position. If a prefix matches target[i:j], update dp[j] with min(dp[j], dp[i] + 1). Efficient prefix checks can be accelerated using structures like a trie or techniques from string matching. The DP table ensures each prefix is solved once, reducing redundant work.
Approach 3: DP with Trie Optimization (O(n * k) time, O(T) space)
When the list of valid strings is large, building a Trie helps speed up prefix lookups. Insert all valid strings into the trie. For each starting index i in the target, walk through the trie while scanning characters forward in the target. Every time you reach a trie node that represents a valid prefix boundary, update dp[j]. This removes repeated string comparisons and limits checks to feasible prefixes only. Time complexity becomes roughly O(n * k), where k is the maximum prefix length explored, while space depends on the trie size.
Recommended for interviews: Start by explaining the recursive idea to show understanding of the search space. Then transition to the dynamic programming solution, which eliminates overlapping work. Interviewers usually expect the DP approach, often combined with a trie or optimized prefix checking, since it demonstrates strong control of string processing, DP state transitions, and scalable design.
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.
Python
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.
Time Complexity: Exponential in theory, reduced to O(t * w * l) due to memoization.
Space Complexity: O(t) for memoization storage.
We can use a trie to store all valid strings and then use memoization to calculate the answer.
We design a function dfs(i), which represents the minimum number of strings needed to concatenate starting from the i-th character of the string target. The answer is dfs(0).
The function dfs(i) is calculated as follows:
i geq n, it means the string target has been completely traversed, so we return 0;target[i], and then recursively calculate dfs(i + len(w)), where w is the valid string found. We take the minimum of these values and add 1 as the return value of dfs(i).To avoid redundant calculations, we use memoization.
The time complexity is O(n^2 + L), and the space complexity is O(n + L). Here, n is the length of the string target, and L is the total length of all valid strings.
Python
Java
C++
Go
TypeScript
| 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. |
| Trie + Memoization | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Backtracking | O(2^n) | O(n) | Understanding the brute force search and validating all possible segmentations |
| Dynamic Programming | O(n * L) | O(n) | General solution for most constraints with predictable performance |
| DP with Trie Optimization | O(n * k) | O(T) | Large dictionary of strings where fast prefix lookup improves performance |
3291 Minimum Number of Valid Strings to Form Target I || How to 🤔 in Interview || Trie + Memo 🥲 • Ayush Rao • 1,843 views views
Watch 3 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