#3291

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Minimum Number of Valid Strings to Form Target I

Use dynamic programming to split target into the fewest prefixes that match any word prefix, while ruling out dead positions early.

array string binary search dynamic programming trie

Problem Statement

You receive a list of words and a target string. A piece is usable whenever it is a prefix of at least one word in the list, so a full word can be used, but so can any shorter starting segment taken from that word.

Your goal is to concatenate the fewest such valid pieces so the final concatenation equals target exactly. If no sequence of valid prefixes can cover target from left to right without mismatch or gaps, the result is -1.

Examples

Example 1

Input: words = ["abc","aaaaa","bcdef"], target = "aabcdabc"

Output: 3

The target string can be formed by concatenating:

Example 2

Input: words = ["abababab","ab"], target = "ababaababa"

Output: 2

The target string can be formed by concatenating:

Example 3

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

Output: -1

Example details omitted.

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.

Solution Approach

Define the DP state on target prefixes

Set dp[i] to the minimum number of valid strings needed to form target[0:i]. Initialize dp[0] = 0 and all other states to a large value. This problem fits state transition dynamic programming because every answer for a longer prefix depends on shorter already-formed prefixes.

Transition by matching valid prefixes at each position

From each index i where dp[i] is reachable, test every word and extend as long as target matches that word starting at i. Every matched length len creates a valid piece because any prefix of the word is allowed, so update dp[i + len] = min(dp[i + len], dp[i] + 1). The key trade-off is that whole-word matching is too strict here; prefix-by-prefix extension is the actual transition rule.

Return the minimum count or detect impossibility

After processing all reachable positions, check dp[target.length]. If it was never updated, return -1. On inputs like words = ["abc","aaaaa","bcdef"] and target = "aabcdabc", the optimal build uses three pieces because greedy longer-prefix picks can still leave a worse suffix, while DP preserves the globally minimum split count.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Let n be target.length and let L be the total length of all words. A direct DP that tries matching each word from each reachable target index runs in roughly O(n * L) in the worst case, because each transition may scan matching characters before stopping. Space is O(n) for the dp array. If you accelerate prefix checks with a trie, rolling hash, or precomputed longest matches, you reduce wasted rescans, but the state definition stays the same: minimum cost to form each target prefix.

What Interviewers Usually Probe

They hint with dp[i] as the minimum cost for the first i target characters, which points directly to prefix DP transitions.
They stress that a valid string is any prefix of a word, signaling that transitions are not limited to full dictionary words.
They include impossible cases like target starting with an unseen letter, testing whether you leave unreachable DP states untouched.

Common Pitfalls or Variants

Common pitfalls

Treating only complete words as usable pieces, which misses valid shorter prefixes and returns counts that are too high or incorrectly -1.
Using greedy longest-prefix choices, which can trap you in a bad suffix even when a shorter current split leads to the true minimum.
Updating dp from every index without checking reachability first, causing meaningless work and hiding why some targets are impossible.

Follow-up variants

Build a trie over words so each target start index walks matching prefixes once instead of rescanning every word.
Precompute the longest valid extension from each target position, then run DP or greedy-style interval expansion on those ranges.
Change the objective from minimum number of pieces to number of ways, which keeps the same state graph but changes the DP aggregation.

FAQ

What is the main pattern in Minimum Number of Valid Strings to Form Target I?

The main pattern is state transition dynamic programming on target prefixes. Each dp[i] stores the fewest valid pieces needed to form the first i characters, and transitions come from every word prefix that matches target starting at i.

Why is this different from classic Word Break?

Classic Word Break usually checks membership of complete dictionary words. In LeetCode 3291, every prefix of every word is allowed, so a match of length 1, 2, 3, and so on can all be legal transitions if they match the target.

Can a greedy longest-prefix strategy solve it?

No, not safely. Taking the longest prefix at one position can force extra splits later, so this problem needs DP to compare all reachable prefix lengths and keep the global minimum.

When should I use a trie here?

A trie helps when many words share prefixes or when repeated character comparisons make the plain DP too slow. It speeds up finding all valid prefix lengths from a target index, but the answer logic still comes from the same dp state.

Why does the answer become -1 for some inputs?

The answer is -1 when no chain of valid prefixes can cover target completely. In DP terms, dp[target.length] stays unreachable because some target position cannot be entered or extended by any matching word prefix.

terminal

Solution

Solution 1: Trie + Memoization

We can use a trie to store all valid strings and then use memoization to calculate the answer.

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

28

29

30

31

32

33

34

35

36

37

38

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

Continue Practicing

#2707 extra characters in a string #3186 maximum total damage with spell casting #2945 find maximum non decreasing array length