2977. Minimum Cost to Convert String II
Description
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:
- The substrings picked in the operations are
source[a..b]
andsource[c..d]
with eitherb < c
ord < a
. In other words, the indices picked in both operations are disjoint. - The substrings picked in the operations are
source[a..b]
andsource[c..d]
witha == c
andb == 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:
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:
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:
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 <= 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
Solutions
Solution 1: Trie + Floyd Algorithm + Memoization Search
According to the problem description, we can consider each string as a node, and the conversion cost between each pair of strings as a directed edge. We first initialize a $26 \times 26$ two-dimensional array $g$, where $g[i][j]$ represents the minimum cost of converting string $i$ to string $j$. Initially, $g[i][j] = \infty$, and if $i = j$, then $g[i][j] = 0$. Here, we can use a trie to store the strings in original
and changed
along with their corresponding integer identifiers.
Next, we use the Floyd algorithm to calculate the minimum cost between any two strings.
Then, we define a function $dfs(i)$ to represent the minimum cost of converting the string $source[i..]$ to the string $target[i..]$. The answer is $dfs(0)$.
The calculation process of the function $dfs(i)$ is as follows:
- If $i \geq |source|$, no conversion is needed, return $0$.
- Otherwise, if $source[i] = target[i]$, we can skip directly and recursively calculate $dfs(i + 1)$. We can also enumerate the index $j$ in the range $[i, |source|)$, if $source[i..j]$ and $target[i..j]$ are both in the trie, and their corresponding integer identifiers $x$ and $y$ are both greater than or equal to $0$, then we can add $dfs(j + 1)$ and $g[x][y]$ to get the cost of one conversion scheme, and we take the minimum value among all schemes.
In summary, we can get:
$$ dfs(i) = \begin{cases} 0, & i \geq |source| \ dfs(i + 1), & source[i] = target[i] \ \min_{i \leq j < |source|} { dfs(j + 1) + g[x][y] }, & \textit{otherwise} \end{cases} $$
Where $x$ and $y$ are the integer identifiers of $source[i..j]$ and $target[i..j]$ in the trie, respectively.
To avoid repeated calculations, we can use memoization search.
The time complexity is $O(m^3 + n^2 + m \times n)$, and the space complexity is $O(m^2 + m \times n + n)$. Where $m$ and $n$ are the lengths of the arrays original
and source
, respectively.
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 |
|