执行结果:通过
题目: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
的最小有效字符串数量。