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 < cord < 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 == candb == 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 <= 1000source,targetconsist only of lowercase English characters.1 <= cost.length == original.length == changed.length <= 1001 <= original[i].length == changed[i].length <= source.lengthoriginal[i],changed[i]consist only of lowercase English characters.original[i] != changed[i]1 <= cost[i] <= 106
Solutions
This solution uses a Trie data structure combined with dynamic programming to find the minimum cost to transform a source string into a target string using allowed character transformations. It first builds a Trie to store all the original-to-changed character pairs and assigns each unique pair an ID, then applies the Floyd-Warshall algorithm to the cost matrix to find the cheapest paths between any two characters through intermediate transformations. Finally, it uses a DP array where resDp[j] represents the minimum cost to transform the first j+1 characters of the source string, iterating through each position and trying all possible substring transformations that exist in the Trie.
class Trie {
constructor() {
this.child = new Array(26).fill(null);
this.id = -1;
}
}
/**
* @param {string} source
* @param {string} target
* @param {string[]} original
* @param {string[]} changed
* @param {number[]} cost
* @return {number}
*/
var minimumCost = (source, target, original, changed, cost) => {
const n = source.length;
const m = original.length;
const root = new Trie();
const pos = { value: -1 };
const nodeCount = m * 2;
const dp = Array.from({ length: nodeCount }, () => Array(nodeCount).fill(Infinity));
for (let i = 0; i < nodeCount; i++) {
dp[i][i] = 0;
}
for (let i = 0; i < m; i++) {
const x = add(root, original[i], pos);
const y = add(root, changed[i], pos);
dp[x][y] = Math.min(dp[x][y], cost[i]);
}
const size = pos.value + 1;
for (let k = 0; k < size; k++) {
for (let i = 0; i < size; i++) {
for (let j = 0; j < size; j++) {
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
}
}
}
const resDp = new Array(n).fill(-1);
for (let j = 0; j < n; j++) {
if (j > 0 && resDp[j - 1] === -1) {
continue;
}
const base = j === 0 ? 0 : resDp[j - 1];
if (source[j] === target[j]) {
if (resDp[j] === -1 || base < resDp[j]) {
resDp[j] = base;
}
}
let u = root;
let v = root;
for (let i = j; i < n; i++) {
u = u.child[source.charCodeAt(i) - "a".charCodeAt(0)];
v = v.child[target.charCodeAt(i) - "a".charCodeAt(0)];
if (!u || !v) {
break;
}
if (u.id !== -1 && v.id !== -1 && dp[u.id][v.id] !== Infinity) {
const newVal = base + dp[u.id][v.id];
if (resDp[i] === -1 || newVal < resDp[i]) {
resDp[i] = newVal;
}
}
}
}
return resDp[n - 1];
};
const add = (node, word, index) => {
for (const ch of word) {
const i = ch.charCodeAt(0) - "a".charCodeAt(0);
if (!node.child[i]) {
node.child[i] = new Trie();
}
node = node.child[i];
}
if (node.id === -1) {
node.id = ++index.value;
}
return node.id;
};