Leetcode打卡：形成目标字符串需要的最少字符串数I

执行结果：通过

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

给你一个字符串数组 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 * 103
• 输入确保 sum(words[i].length) <= 105。
• words[i] 只包含小写英文字母。
• 1 <= target.length <= 5 * 103
• target 只包含小写英文字母。

代码以及解题思路

代码：

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

解题思路：

1. 定义辅助数据结构：
   • 使用一个自定义的 Trie（前缀树）数据结构来存储所有可能的单词前缀。Trie 的每个节点有 26 个子节点（对应 26 个英文字母），每个子节点要么为 None（表示该路径不存在），要么指向另一个 Trie 节点（表示该路径存在）。
2. 构建 Trie：
   • 遍历 words 列表，将每个单词插入到 Trie 中。对于单词中的每个字符，将其转换为对应的索引（通过 ord(c) - 97，这里假设所有字符都是小写字母 a 到 z），并沿着这个索引在 Trie 中移动或创建新的节点。
3. 深度优先搜索（DFS）：
   • 定义一个递归函数 dfs(i: int)，其中 i 表示当前正在考虑的 target 字符串的索引。
   • 如果 i 达到了 target 的长度，意味着已经成功遍历了整个 target 字符串，返回 0（因为不需要额外的单词）。
   • 初始化一个变量 ans 为无穷大（inf），用于存储最小的单词数量。
   • 从当前索引 i 开始，尝试向后遍历 target 字符串，每次移动一个字符，并在 Trie 中查找该字符的路径。
   • 如果在某个位置，Trie 中不存在对应的路径，则停止进一步遍历。
   • 如果路径存在，继续递归调用 dfs 函数，从下一个字符开始，并将当前使用的一个单词（通过 1 + dfs(j + 1) 表示）加到答案中。
   • 更新 ans 为所有可能路径中的最小值。
4. 处理结果：
   • 执行 DFS 搜索，从 target 的第一个字符开始。
   • 如果最终得到的 ans 仍然是无穷大（inf），则表示无法通过 words 列表中的单词完全构成 target，返回 -1。
   • 否则，返回 ans，即构成 target 的最少单词数量。
5. 性能优化：
   • 使用 @cache 装饰器来缓存递归函数 dfs 的结果，避免重复计算，从而提高性能。

总结来说，这段代码通过构建一个前缀树（Trie）来高效地检查哪些单词前缀是存在的，然后使用深度优先搜索（DFS）来尝试所有可能的组合，以找到构成目标字符串所需的最少单词数量。