Minimum Number of Valid Strings to Form Target I
MedPrompt
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:
- Prefix of length 2 of
words[1], i.e."aa". - Prefix of length 3 of
words[2], i.e."bcd". - Prefix of length 3 of
words[0], i.e."abc".
Example 2:
Input: words = ["abababab","ab"], target = "ababaababa"
Output: 2
Explanation:
The target string can be formed by concatenating:
- Prefix of length 5 of
words[0], i.e."ababa". - Prefix of length 5 of
words[0], i.e."ababa".
Example 3:
Input: words = ["abcdef"], target = "xyz"
Output: -1
Constraints:
1 <= words.length <= 1001 <= words[i].length <= 5 * 103- The input is generated such that
sum(words[i].length) <= 105. words[i]consists only of lowercase English letters.1 <= target.length <= 5 * 103targetconsists only of lowercase English letters.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses dynamic programming combined with a hash set. We pre-compute all valid prefixes from the words array and store them in a hash set for fast lookups. Then, we use a DP array dp[i] to store the minimum number of strings to form the first i characters of the target. The DP state is updated by checking all possible last valid strings ending at each position.
Algorithm
- Create a
HashSet<String>to store all valid prefixes. - Iterate through each word in
words, generate all its prefixes, and add them to the hash set. - Initialize a DP array
dpof sizetarget.length() + 1with a large value, and setdp[0] = 0. - Use nested loops to iterate through all substrings
target.substring(j, i). - If
dp[j]is reachable andtarget.substring(j, i)is in the hash set, updatedp[i]withmin(dp[i], dp[j] + 1). - The final answer is
dp[target.length()], or -1 if it's still the large value.
Walkthrough
The core of this method is the dynamic programming recurrence: dp[i] = min(dp[j] + 1) over all j < i such that target.substring(j, i) is a valid prefix. To make the check for a valid prefix efficient, we first populate a HashSet with all prefixes of every word in the input words. This pre-computation step allows us to check if any given substring is a valid prefix in approximately constant time on average (though proportional to the substring's length due to hashing).
The main DP loop then iterates through all possible end-points i of a prefix of target, and for each i, it tries all possible start-points j. If target.substring(j, i) is found in our pre-computed set, we have a potential way to form target.substring(0, i), and we update dp[i] accordingly.
import java.util.Arrays;import java.util.HashSet;import java.util.Set; class Solution { public int minStrings(String[] words, String target) { Set<String> validPrefixes = new HashSet<>(); for (String word : words) { for (int k = 1; k <= word.length(); k++) { validPrefixes.add(word.substring(0, k)); } } int n = target.length(); int[] dp = new int[n + 1]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (dp[j] != Integer.MAX_VALUE) { String sub = target.substring(j, i); if (validPrefixes.contains(sub)) { dp[i] = Math.min(dp[i], dp[j] + 1); } } } } return dp[n] == Integer.MAX_VALUE ? -1 : dp[n]; }}Complexity
Time
O(S_W * L + n^3), where `n` is `target.length()`, `S_W` is `sum(words[i].length)`, and `L` is the max word length. Pre-computation is `O(S_W * L)`. The DP part is `O(n^3)` because of `O(n^2)` states and `O(n)` work per state for substring creation and hashing.
Space
O(S_W * L + n). The hash set can store prefixes whose total length is up to `O(S_W * L)`, where `S_W` is the sum of lengths of words and `L` is the maximum word length. The DP array takes `O(n)` space.
Trade-offs
Pros
Conceptually simpler than using a Trie.
Straightforward implementation of the DP recurrence.
Cons
High time complexity makes it too slow for the given constraints.
High space complexity if words are long and numerous.
Solutions
Solution
class Trie { Trie [] children = new Trie [ 26 ]; void insert ( String w ) { Trie node = this ; for ( int i = 0 ; i < w . length (); ++ i ) { int j = w . charAt ( i ) - 'a' ; if ( node . children [ j ] == null ) { node . children [ j ] = new Trie (); } node = node . children [ j ]; } } } class Solution { private Integer [] f ; private char [] s ; private Trie trie ; private final int inf = 1 << 30 ; public int minValidStrings ( String [] words , String target ) { trie = new Trie (); for ( String w : words ) { trie . insert ( w ); } s = target . toCharArray (); f = new Integer [ s . length ]; int ans = dfs ( 0 ); return ans < inf ? ans : - 1 ; } private int dfs ( int i ) { if ( i >= s . length ) { return 0 ; } if ( f [ i ] != null ) { return f [ i ]; } Trie node = trie ; f [ i ] = inf ; for ( int j = i ; j < s . length ; ++ j ) { int k = s [ j ] - 'a' ; if ( node . children [ k ] == null ) { break ; } f [ i ] = Math . min ( f [ i ], 1 + dfs ( j + 1 )); node = node . children [ k ]; } return f [ i ]; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.