3238 Minimum Cost To Convert String Ii
3238 Minimum Cost To Convert String Ii
Minimum Cost to Convert String II 
You are given two 0-indexed strings source and target, both of length n and consisting of lowercase English characters. You are also given two 0-indexed string arrays original and changed, and an integer array cost, where cost[i] represents the cost of converting the string original[i] to the string changed[i].
You start with the string source. In one operation, you can pick a substring x from the string, and change it to y at a cost of z if there exists any index j such that cost[j] == z, original[j] == x, and changed[j] == y. You are allowed to do any number of operations, but any pair of operations must satisfy either of these two conditions:
1
2
The substrings picked in the operations are source[a..b] and source[c..d] with either b < c **or** d < a. In other words, the indices picked in both operations are **disjoint**.
The substrings picked in the operations are source[a..b] and source[c..d] with a == c **and** b == d. In other words, the indices picked in both operations are **identical**.
Return the minimum cost to convert the string *source to the string target using any number of operations. *If it is impossible to convert source to target,* return* -1.
Note that there may exist indices i, j such that original[j] == original[i] and changed[j] == changed[i].
Example 1:
1
2
3
4
5
6
7
8
9
10
11
**Input:** source = "abcd", target = "acbe", original = ["a","b","c","c","e","d"], changed = ["b","c","b","e","b","e"], cost = [2,5,5,1,2,20]
**Output:** 28
**Explanation:** To convert "abcd" to "acbe", do the following operations:
- Change substring source[1..1] from "b" to "c" at a cost of 5.
- Change substring source[2..2] from "c" to "e" at a cost of 1.
- Change substring source[2..2] from "e" to "b" at a cost of 2.
- Change substring source[3..3] from "d" to "e" at a cost of 20.
The total cost incurred is 5 + 1 + 2 + 20 = 28.
It can be shown that this is the minimum possible cost.
Example 2:
1
2
3
4
5
6
7
8
9
10
**Input:** source = "abcdefgh", target = "acdeeghh", original = ["bcd","fgh","thh"], changed = ["cde","thh","ghh"], cost = [1,3,5]
**Output:** 9
**Explanation:** To convert "abcdefgh" to "acdeeghh", do the following operations:
- Change substring source[1..3] from "bcd" to "cde" at a cost of 1.
- Change substring source[5..7] from "fgh" to "thh" at a cost of 3. We can do this operation because indices [5,7] are disjoint with indices picked in the first operation.
- Change substring source[5..7] from "thh" to "ghh" at a cost of 5. We can do this operation because indices [5,7] are disjoint with indices picked in the first operation, and identical with indices picked in the second operation.
The total cost incurred is 1 + 3 + 5 = 9.
It can be shown that this is the minimum possible cost.
Example 3:
1
2
3
4
5
6
7
**Input:** source = "abcdefgh", target = "addddddd", original = ["bcd","defgh"], changed = ["ddd","ddddd"], cost = [100,1578]
**Output:** -1
**Explanation:** It is impossible to convert "abcdefgh" to "addddddd".
If you select substring source[1..3] as the first operation to change "abcdefgh" to "adddefgh", you cannot select substring source[3..7] as the second operation because it has a common index, 3, with the first operation.
If you select substring source[3..7] as the first operation to change "abcdefgh" to "abcddddd", you cannot select substring source[1..3] as the second operation because it has a common index, 3, with the first operation.
Constraints:
1
2
3
4
5
6
7
1 <= source.length == target.length <= 1000
source, target consist only of lowercase English characters.
1 <= cost.length == original.length == changed.length <= 100
1 <= original[i].length == changed[i].length <= source.length
original[i], changed[i] consist only of lowercase English characters.
original[i] != changed[i]
1 <= cost[i] <= 106
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
INF = 10**18
INF_INT = 10**9
class Solution:
def minimumCost(
self,
source: str,
target: str,
original: List[str],
changed: List[str],
cost: List[int],
) -> int:
n = len(source)
m = len(original)
child = [[-1] * 26]
tid = [-1]
def new_node() -> int:
child.append([-1] * 26)
tid.append(-1)
return len(child) - 1
idx = -1
def add(word: str) -> int:
nonlocal idx
node = 0
for ch in word:
c = ord(ch) - 97
nxt = child[node][c]
if nxt == -1:
nxt = new_node()
child[node][c] = nxt
node = nxt
if tid[node] == -1:
idx += 1
tid[node] = idx
return tid[node]
edges = []
for i in range(m):
x = add(original[i])
y = add(changed[i])
edges.append((x, y, cost[i]))
P = idx + 1
if P == 0:
return 0 if source == target else -1
dist = [[INF_INT] * P for _ in range(P)]
for i in range(P):
dist[i][i] = 0
for x, y, w in edges:
if w < dist[x][y]:
dist[x][y] = w
for k in range(P):
dk = dist[k]
for i in range(P):
di = dist[i]
dik = di[k]
if dik == INF_INT:
continue
base = dik
for j in range(P):
nd = base + dk[j]
if nd < di[j]:
di[j] = nd
dp = [INF] * (n + 1)
dp[0] = 0
s_arr = [ord(c) - 97 for c in source]
t_arr = [ord(c) - 97 for c in target]
for j in range(n):
if dp[j] >= INF:
continue
base = dp[j]
if source[j] == target[j] and base < dp[j + 1]:
dp[j + 1] = base
u = 0
v = 0
for i in range(j, n):
u = child[u][s_arr[i]]
v = child[v][t_arr[i]]
if u == -1 or v == -1:
break
uid = tid[u]
vid = tid[v]
if uid != -1 and vid != -1:
w = dist[uid][vid]
if w != INF_INT:
ni = i + 1
cand = base + w
if cand < dp[ni]:
dp[ni] = cand
ans = dp[n]
return -1 if ans >= INF else ans
This post is licensed under CC BY 4.0 by the author.