力扣第 405 场周赛第 4 题
题目
给你一个字符串 target、一个字符串数组 words 以及一个整数数组 costs，这两个数组长度相同。
设想一个空字符串 s。
你可以执行以下操作任意次数（包括 零 次）：
- 选择一个在范围
[0, words.length - 1] 的索引 i。
- 将
words[i] 追加到 s。
- 该操作的成本是
costs[i]。
返回使 s 等于 target 的 最小 成本。如果不可能，返回 -1。
示例 1：
输入： target = "abcdef", words = ["abdef","abc","d","def","ef"], costs = [100,1,1,10,5]
输出： 7
解释：
- 选择索引 1 并以成本 1 将
"abc" 追加到 s，得到 s = "abc"。
- 选择索引 2 并以成本 1 将
"d" 追加到 s，得到 s = "abcd"。
- 选择索引 4 并以成本 5 将
"ef" 追加到 s，得到 s = "abcdef"。
示例 2：
输入： target = "aaaa", words = ["z","zz","zzz"], costs = [1,10,100]
输出： -1
解释：
无法使 s 等于 target，因此返回 -1。
提示：
1 <= target.length <= 5 * 1041 <= words.length == costs.length <= 5 * 1041 <= words[i].length <= target.length- 所有
words[i].length 的总和小于或等于 5 * 104
target 和 words[i] 仅由小写英文字母组成。1 <= costs[i] <= 104
相似问题：
分析
解答
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
class Node:
__slots__ = 'son', 'fail', 'last', 'sz', 'w'
def __init__(self):
self.son = [None] * 26
self.fail = None # u 的 fail 指向 v，v 是树中 u 的最长后缀
self.last = None # u 的 last 指向 v，v 是树中 u 的最长后缀且是某个单词的结尾
self.sz = 0 # 假如 u 是某个单词的结尾，sz 即是单词长度
self.w = inf # 假如 u 是某个单词的结尾，w 即是单词成本
class AC:
def __init__(self):
self.root = p = Node()
dum = Node() # 哑节点，方便后续 build
dum.son, p.fail, p.last = [p]*26, dum, p
def add(self,s,w):
p = self.root
for c in s:
c = ord(c) - ord('a')
if not p.son[c]:
p.son[c] = Node()
p = p.son[c]
p.sz = len(s)
p.w = min(p.w,w)
def build(self):
Q = deque([self.root])
while Q:
u = Q.popleft()
for c,son in enumerate(u.son):
if son:
son.fail = u.fail.son[c]
son.last = son.fail if son.fail.sz else son.fail.last
Q.append(son)
else: # 虚拟子节点，失配时直接跳到下一个匹配位置
u.son[c] = u.fail.son[c]
class Solution:
def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
ac = AC()
for s,w in zip(words,costs):
ac.add(s,w)
ac.build()
n = len(target)
f = [0]+[inf]*n
p = root = ac.root
for i in range(1,n+1):
c = ord(target[i-1])-ord('a')
p = p.son[c]
if p.sz:
f[i] = min(f[i],f[i-p.sz]+p.w)
u = p.last
while u!=root:
tmp = f[i-u.sz]+u.w
if tmp<f[i]:
f[i] = tmp
u = u.last
return f[-1] if f[-1]<inf else -1
|
6650 ms
*附加
- AC 自动机还可以用数组形式
- py 用 [n] * 26 的数组比 [26] * n 的数组快很多，所以要绕一些
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
class AC:
def __init__(self,n): # 总长度 n-1 的字符串
self.son = [[0]*n for _ in range(26)]
self.fail = [0]*n
self.last = [0]*n
self.sz = [0]*n
self.w = [inf]*n
self.i = 0
def add(self,s,w):
p = 0
for c in s:
c = ord(c)-ord('a')
if not self.son[c][p]:
self.son[c][p] = self.i = self.i+1
p = self.son[c][p]
self.sz[p] = len(s)
self.w[p] = min(self.w[p],w)
def build(self):
Q = deque(A[0] for A in self.son if A[0])
while Q:
u = Q.popleft()
for A in self.son:
if A[u]:
v = self.fail[A[u]] = A[self.fail[u]]
self.last[A[u]] = v if self.sz[v] else self.last[v]
Q.append(A[u])
else: # 虚拟子节点，失配时直接跳到下一个匹配位置
A[u] = A[self.fail[u]]
class Solution:
def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
ac = AC(sum(len(s) for s in words)+1)
for s,w in zip(words,costs):
ac.add(s,w)
ac.build()
n = len(target)
f = [0]+[inf]*n
p = 0
for i in range(1,n+1):
c = ord(target[i-1])-ord('a')
p = ac.son[c][p]
if ac.sz[p]:
f[i] = min(f[i],f[i-ac.sz[p]]+ac.w[p])
u = ac.last[p]
while u:
tmp = f[i-ac.sz[u]]+ac.w[u]
if tmp<f[i]:
f[i] = tmp
u = ac.last[u]
return f[-1] if f[-1]<inf else -1
|
5657 ms