新疆生产建设兵团第十二师_微信小程序怎么做链接_关键词优化是什么意思?_谷歌广告投放

执行结果：通过

题目：3292 形成目标字符串需要的最少字符串数II

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

代码以及解题思路

代码

class Solution:def minValidStrings(self, words: List[str], target: str) -> int:n = reduce(lambda a, b: a + len(b), words, 1)ac = AC(n)for i, word in enumerate(words):ac.insert(word, 1)ac.build()ans = ac.search(target)return ans
class AC:def __init__(self, N: int):self.tot = 0self.tr = [[0] * 26 for _ in range(N)]self.e = [0] * N self.cost = [1] * Nself.len = [0] * Nself.fail = [0] * Nself.last = [0] * Ndef insert(self, word: str, cost: int) -> None:u = 0for i, ch in enumerate(word):ch = ord(ch) - ord("a")if self.tr[u][ch] == 0:self.tot += 1self.tr[u][ch] = self.totu = self.tr[u][ch]self.len[u] = i + 1self.e[u] += 1def build(self) -> None:dq = deque()for i in range(26):if self.tr[0][i] != 0:dq.append(self.tr[0][i])while dq:u = dq.popleft()for i in range(26):if self.tr[u][i] != 0:self.fail[self.tr[u][i]] = self.tr[self.fail[u]][i]self.last[self.tr[u][i]] = self.fail[self.tr[u][i]] if self.len[self.fail[self.tr[u][i]]] else self.last[self.fail[self.tr[u][i]]]dq.append(self.tr[u][i])else:self.tr[u][i] = self.tr[self.fail[u]][i]def search(self, word: str) -> int:n = len(word)dp = [0] * (n+1)u = 0for i in range(1, n+1):ch = ord(word[i-1]) - ord("a")u = self.tr[u][ch]if u == 0:return -1dp[i] = dp[i - self.len[u]] + 1return dp[n]

解题思路：

初始化 AC 自动机：
- AC 自动机是一种用于多模式字符串匹配的数据结构，可以看作是一个Trie（前缀树）与KMP（Knuth-Morris-Pratt）算法的结合。
- 初始化时，需要构建一个Trie树，并添加失败指针（fail指针），使得在匹配失败时可以跳转到另一个状态继续匹配。
构建 AC 自动机：
- 将所有单词插入到Trie树中，并记录每个节点的信息，如节点对应的字符串长度、是否是某个单词的结尾等。
- 使用广度优先搜索（BFS）构建失败指针，使得每个节点在匹配失败时可以跳转到另一个节点继续匹配。
动态规划求解最小有效字符串数量：
- 使用动态规划数组 dp，其中 dp[i] 表示形成 target 的前 i 个字符所需的最小有效字符串数量。
- 遍历 target 的每个字符，利用AC自动机在Trie树中查找当前字符可能匹配的最长前缀。
- 更新 dp[i] 为 dp[i - len(匹配的前缀)] + 1，表示通过添加一个有效字符串（包含当前匹配的前缀）来形成 target 的前 i 个字符。
- 如果在某个位置无法匹配任何前缀（即AC自动机的当前状态为0），则无法形成 target，返回 -1。
返回结果：
- 遍历完成后，dp[n]（n 是 target 的长度）即为形成整个 target 所需的最小有效字符串数量。

代码细节

reduce(lambda a, b: a + len(b), words, 1)：计算所有单词的总长度，用于初始化AC自动机的大小。
AC 类：实现了AC自动机的构建和搜索功能。
- insert 方法：将单词插入Trie树。
- build 方法：构建失败指针。
- search 方法：使用动态规划搜索形成 target 的最小有效字符串数量。