# Minimum Number of Valid Strings to Form Target I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-number-of-valid-strings-to-form-target-i)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-valid-strings-to-form-target-i
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [String Matching](https://scaleengineer.com/dsa/patterns/string-matching), [Rolling Hash](https://scaleengineer.com/dsa/patterns/rolling-hash), [Hash Function](https://scaleengineer.com/dsa/patterns/hash-function)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, String, Trie, Segment Tree
---
## Problem
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 <= 100`
* `1 <= 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 * 103`
* `target` consists only of lowercase English letters.

# Approaches
## Dynamic Programming with Hash Set
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.
**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.
**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.
### Explanation
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.

```java
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];
    }
}
```
### 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 `dp` of size `target.length() + 1` with a large value, and set `dp[0] = 0`.
- Use nested loops to iterate through all substrings `target.substring(j, i)`.
- If `dp[j]` is reachable and `target.substring(j, i)` is in the hash set, update `dp[i]` with `min(dp[i], dp[j] + 1)`.
- The final answer is `dp[target.length()]`, or -1 if it's still the large value.

## Dynamic Programming with Trie
This optimized approach uses dynamic programming with a Trie (prefix tree). Instead of a hash set, a Trie is built from all the words in `words`. This data structure is ideal for prefix-based searches. The DP logic is enhanced: for each position `i` in the target, we traverse the Trie with subsequent characters `target[j]` (`j >= i`). Each time we find a valid prefix in the Trie, we update the DP state for the corresponding end position `j+1`.
**Time:** O(S_W + n^2), where `n` is `target.length()` and `S_W` is `sum(words[i].length)`. Building the Trie is `O(S_W)`. The DP calculation is `O(n^2)` due to the nested loops with constant time work inside. · **Space:** O(S_W + n). The Trie requires `O(S_W)` space, where `S_W` is the sum of lengths of all words. The DP array takes `O(n)` space.
**Pros:** Highly efficient with O(n^2) time complexity, suitable for the given constraints.; Trie is the optimal data structure for prefix-based problems.
**Cons:** Requires implementation of a Trie data structure, which adds some complexity.
### Explanation
This method significantly improves performance by replacing the hash set with a Trie. A Trie stores the dictionary of words in a way that all prefixes can be checked efficiently. We first insert all words from the `words` array into the Trie. 

Then, we apply dynamic programming. We iterate through the `target` string with an index `i`. If `dp[i]` is reachable (not infinity), it means we have successfully formed `target.substring(0, i)`. From this point, we try to extend our solution by finding the next valid string. We do this by starting a search from the Trie's root with characters `target[i], target[i+1], ...`. For every character `target[j]` that corresponds to a valid path in the Trie, we know `target.substring(i, j+1)` is a valid prefix. This allows us to update `dp[j+1]` with `dp[i] + 1`. This avoids the expensive substring creation and hashing at each step of the inner loop.

```java
import java.util.Arrays;

class Solution {
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
    }

    public int minStrings(String[] words, String target) {
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode curr = root;
            for (char c : word.toCharArray()) {
                if (curr.children[c - 'a'] == null) {
                    curr.children[c - 'a'] = new TrieNode();
                }
                curr = curr.children[c - 'a'];
            }
        }

        int n = target.length();
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 0; i < n; i++) {
            if (dp[i] == Integer.MAX_VALUE) {
                continue;
            }
            
            TrieNode curr = root;
            for (int j = i; j < n; j++) {
                char c = target.charAt(j);
                if (curr.children[c - 'a'] == null) {
                    break; // Not a valid prefix
                }
                curr = curr.children[c - 'a'];
                // Since any prefix is valid, we can make a cut here
                dp[j + 1] = Math.min(dp[j + 1], dp[i] + 1);
            }
        }

        return dp[n] == Integer.MAX_VALUE ? -1 : dp[n];
    }
}
```
### Algorithm
- Define a `TrieNode` class.
- Build a Trie by inserting all words from the `words` array.
- Initialize a DP array `dp` of size `target.length() + 1` with a large value, and set `dp[0] = 0`.
- Iterate `i` from 0 to `n-1`. If `dp[i]` is reachable:
  - Start a traversal from the Trie root.
  - Iterate `j` from `i` to `n-1`, traversing the Trie with `target.charAt(j)`.
  - If the path is valid, update `dp[j+1]` with `min(dp[j+1], dp[i] + 1)`.
  - If the path breaks, stop the inner traversal.
- The final answer is `dp[target.length()]`, or -1 if it's unreachable.

# Solutions
### Java

```java
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 ]; } }
```

### CPP

```cpp
class Trie { public: Trie * children [ 26 ]{}; void insert ( string & word ) { Trie * node = this ; for ( char & c : word ) { int i = c - 'a' ; if ( ! node -> children [ i ]) { node -> children [ i ] = new Trie (); } node = node -> children [ i ]; } } }; class Solution { public: int minValidStrings ( vector < string >& words , string target ) { int n = target . size (); Trie * trie = new Trie (); for ( auto & w : words ) { trie -> insert ( w ); } const int inf = 1 << 30 ; int f [ n ]; memset ( f , - 1 , sizeof ( f )); auto dfs = [ & ]( auto && dfs , int i ) -> int { if ( i >= n ) { return 0 ; } if ( f [ i ] != - 1 ) { return f [ i ]; } f [ i ] = inf ; Trie * node = trie ; for ( int j = i ; j < n ; ++ j ) { int k = target [ j ] - 'a' ; if ( ! node -> children [ k ]) { break ; } node = node -> children [ k ]; f [ i ] = min ( f [ i ], 1 + dfs ( dfs , j + 1 )); } return f [ i ]; }; int ans = dfs ( dfs , 0 ); return ans < inf ? ans : - 1 ; } };
```

### Python

```python
def min ( a : int , b : int ) -> int : return a if a < b else b class Trie : def __init__ ( self ): self . children : List [ Optional [ Trie ]] = [ None ] * 26 def insert ( self , w : str ): node = self for i in map ( lambda c : ord ( c ) - 97 , w ): if node . children [ i ] is None : node . children [ i ] = Trie () node = node . children [ i ] class Solution : def minValidStrings ( self , words : List [ str ], target : str ) -> int : @ cache def dfs ( i : int ) -> int : if i >= n : return 0 node = trie ans = inf for j in range ( i , n ): k = ord ( target [ j ]) - 97 if node . children [ k ] is None : break node = node . children [ k ] ans = min ( ans , 1 + dfs ( j + 1 )) return ans trie = Trie () for w in words : trie . insert ( w ) n = len ( target ) ans = dfs ( 0 ) return ans if ans < inf else - 1
```