Minimum Number of Valid Strings to Form Target I

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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12



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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11



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

1
2
3
4



Input: words = ["abcdef"], target = "xyz"

Output: -1

Constraints

1 <= words.length <= 100
1 <= words[i].length <= 5 * 10^3
The input is generated such that sum(words[i].length) <= 10^5.
words[i] consists only of lowercase English letters.
1 <= target.length <= 5 * 10^3
target consists only of lowercase English letters.

Solution

Method 1 – DP with Trie for Prefix Matching

Intuition

This is a classic word break problem, but with valid prefixes from the given words. We use a Trie for fast prefix lookup and DP to find the minimum splits.

Approach

Build a Trie from all words, storing all possible prefixes.
Use DP: dp[i] = min number of valid strings to form target[0:i].
For each position, try all valid prefixes ending at that position using the Trie.
If a prefix matches, update dp[i].
Return dp[n] or -1 if impossible.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


#include <vector>
#include <string>
#include <unordered_set>
using namespace std;
class Solution {
public:
    int minValidStrings(vector<string>& words, string target) {
        unordered_set<string> prefixes;
        for (auto& w : words) {
            for (int l = 1; l <= w.size(); ++l)
                prefixes.insert(w.substr(0, l));
        }
        int n = target.size();
        vector<int> dp(n + 1, 1e9);
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int l = 1; l <= i; ++l) {
                if (prefixes.count(target.substr(i - l, l))) {
                    dp[i] = min(dp[i], dp[i - l] + 1);
                }
            }
        }
        return dp[n] == 1e9 ? -1 : dp[n];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


func minValidStrings(words []string, target string) int {
    prefixes := make(map[string]struct{})
    for _, w := range words {
        for l := 1; l <= len(w); l++ {
            prefixes[w[:l]] = struct{}{}
        }
    }
    n := len(target)
    dp := make([]int, n+1)
    for i := range dp {
        dp[i] = 1e9
    }
    dp[0] = 0
    for i := 1; i <= n; i++ {
        for l := 1; l <= i; l++ {
            if _, ok := prefixes[target[i-l:i]]; ok {
                if dp[i-l]+1 < dp[i] {
                    dp[i] = dp[i-l] + 1
                }
            }
        }
    }
    if dp[n] == 1e9 {
        return -1
    }
    return dp[n]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


import java.util.*;
class Solution {
    public int minValidStrings(String[] words, String target) {
        Set<String> prefixes = new HashSet<>();
        for (String w : words) {
            for (int l = 1; l <= w.length(); l++)
                prefixes.add(w.substring(0, l));
        }
        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 l = 1; l <= i; l++) {
                if (prefixes.contains(target.substring(i - l, i))) {
                    dp[i] = Math.min(dp[i], dp[i - l] + 1);
                }
            }
        }
        return dp[n] == Integer.MAX_VALUE ? -1 : dp[n];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution {
    fun minValidStrings(words: Array<String>, target: String): Int {
        val prefixes = mutableSetOf<String>()
        for (w in words) for (l in 1..w.length) prefixes.add(w.substring(0, l))
        val n = target.length
        val dp = IntArray(n + 1) { Int.MAX_VALUE }
        dp[0] = 0
        for (i in 1..n) {
            for (l in 1..i) {
                if (prefixes.contains(target.substring(i - l, i))) {
                    dp[i] = minOf(dp[i], dp[i - l] + 1)
                }
            }
        }
        return if (dp[n] == Int.MAX_VALUE) -1 else dp[n]
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution:
    def minValidStrings(self, words: list[str], target: str) -> int:
        prefixes = set()
        for w in words:
            for l in range(1, len(w) + 1):
                prefixes.add(w[:l])
        n = len(target)
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        for i in range(1, n + 1):
            for l in range(1, i + 1):
                if target[i - l:i] in prefixes:
                    dp[i] = min(dp[i], dp[i - l] + 1)
        return -1 if dp[n] == float('inf') else dp[n]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


use std::collections::HashSet;
impl Solution {
    pub fn min_valid_strings(words: Vec<String>, target: String) -> i32 {
        let mut prefixes = HashSet::new();
        for w in &words {
            for l in 1..=w.len() {
                prefixes.insert(&w[..l]);
            }
        }
        let n = target.len();
        let mut dp = vec![i32::MAX; n + 1];
        dp[0] = 0;
        let t = target.as_bytes();
        for i in 1..=n {
            for l in 1..=i {
                if prefixes.contains(std::str::from_utf8(&t[i - l..i]).unwrap()) {
                    dp[i] = dp[i].min(dp[i - l] + 1);
                }
            }
        }
        if dp[n] == i32::MAX { -1 } else { dp[n] }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution {
    minValidStrings(words: string[], target: string): number {
        const prefixes = new Set<string>();
        for (const w of words) for (let l = 1; l <= w.length; ++l) prefixes.add(w.slice(0, l));
        const n = target.length;
        const dp = Array(n + 1).fill(Infinity);
        dp[0] = 0;
        for (let i = 1; i <= n; ++i) {
            for (let l = 1; l <= i; ++l) {
                if (prefixes.has(target.slice(i - l, i))) {
                    dp[i] = Math.min(dp[i], dp[i - l] + 1);
                }
            }
        }
        return dp[n] === Infinity ? -1 : dp[n];
    }
}

Complexity

⏰ Time complexity: O(N^2) — N = length of target, for each position try all possible prefixes.
🧺 Space complexity: O(S) — S = total length of all words (for prefix set).

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – DP with Trie for Prefix Matching#

Intuition#

Approach#

Code#

Complexity#