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.

#3291

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

形成目标字符串需要的最少字符串数 I

给你一个字符串数组 words 和一个字符串 target 。如果字符串 x 是 words 中任意字符串的前缀，则认为 x 是一个有效字符串。现计划通过连接有效字符串形成 target ，请你计算并返回需要连接的最少字符串数量。如果无法通过这种方式形成 target ，则返…

数组字符串二分查找动态规划字典树

题目描述

给你一个字符串数组 words 和一个字符串 target。

如果字符串 x 是 words 中任意字符串的前缀，则认为 x 是一个有效字符串。

现计划通过连接有效字符串形成 target ，请你计算并返回需要连接的最少字符串数量。如果无法通过这种方式形成 target，则返回 -1。

示例 1：

输入： words = ["abc","aaaaa","bcdef"], target = "aabcdabc"

输出： 3

解释：

target 字符串可以通过连接以下有效字符串形成：

words[1] 的长度为 2 的前缀，即 "aa"。
words[2] 的长度为 3 的前缀，即 "bcd"。
words[0] 的长度为 3 的前缀，即 "abc"。

示例 2：

输入： words = ["abababab","ab"], target = "ababaababa"

输出： 2

解释：

target 字符串可以通过连接以下有效字符串形成：

words[0] 的长度为 5 的前缀，即 "ababa"。
words[0] 的长度为 5 的前缀，即 "ababa"。

示例 3：

输入： words = ["abcdef"], target = "xyz"

输出： -1

提示：

1 <= words.length <= 100
1 <= words[i].length <= 5 * 10³
输入确保 sum(words[i].length) <= 10⁵。
words[i] 只包含小写英文字母。
1 <= target.length <= 5 * 10³
target 只包含小写英文字母。

lightbulb

解题思路

方法一：字典树 + 记忆化搜索

我们可以使用字典树存储所有有效字符串，然后使用记忆化搜索计算答案。

我们设计一个函数 $\textit{dfs}(i)$ ，表示从字符串 $\textit{target}$ 的第 $i$ 个字符开始，需要连接的最少字符串数量。那么答案就是 $\textit{dfs}(0)$ 。

函数 $\textit{dfs}(i)$ 的计算方式如下：

如果 $i \geq n$ ，表示字符串 $\textit{target}$ 已经遍历完了，返回 $0$ ；
否则，我们可以从字典树中找到以 $\textit{target}[i]$ 开头的有效字符串，然后递归计算 $\textit{dfs}(i + \text{len}(w))$ ，其中 $w$ 是找到的有效字符串。我们取这些值中的最小值加 $1$ 作为 $\textit{dfs}(i)$ 的返回值。

为了避免重复计算，我们使用记忆化搜索。

时间复杂度 $O(n^2 + L)$ ，空间复杂度 $O(n + L)$ 。其中 $n$ 是字符串 $\textit{target}$ 的长度，而 $L$ 是所有有效字符串的总长度。

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

39

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#2707 字符串中的额外字符 #3186 施咒的最大总伤害 #2945 找到最大非递减数组的长度