| comments | difficulty | edit_url | rating | source | tags | ||||
|---|---|---|---|---|---|---|---|---|---|
true |
Medium |
1882 |
Weekly Contest 377 Q3 |
|
You are given two 0-indexed strings source and target, both of length n and consisting of lowercase English letters. You are also given two 0-indexed character arrays original and changed, and an integer array cost, where cost[i] represents the cost of changing the character original[i] to the character changed[i].
You start with the string source. In one operation, you can pick a character x from the string and change it to the character y at a cost of z if there exists any index j such that cost[j] == z, original[j] == x, and changed[j] == y.
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 the string "abcd" to string "acbe": - Change value at index 1 from 'b' to 'c' at a cost of 5. - Change value at index 2 from 'c' to 'e' at a cost of 1. - Change value at index 2 from 'e' to 'b' at a cost of 2. - Change value at index 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 = "aaaa", target = "bbbb", original = ["a","c"], changed = ["c","b"], cost = [1,2] Output: 12 Explanation: To change the character 'a' to 'b' change the character 'a' to 'c' at a cost of 1, followed by changing the character 'c' to 'b' at a cost of 2, for a total cost of 1 + 2 = 3. To change all occurrences of 'a' to 'b', a total cost of 3 * 4 = 12 is incurred.
Example 3:
Input: source = "abcd", target = "abce", original = ["a"], changed = ["e"], cost = [10000] Output: -1 Explanation: It is impossible to convert source to target because the value at index 3 cannot be changed from 'd' to 'e'.
Constraints:
1 <= source.length == target.length <= 105source,targetconsist of lowercase English letters.1 <= cost.length == original.length == changed.length <= 2000original[i],changed[i]are lowercase English letters.1 <= cost[i] <= 106original[i] != changed[i]
According to the problem description, we can consider each letter as a node, and the conversion cost between each pair of letters as a directed edge. We first initialize a
Next, we traverse the arrays
Then, we use the Floyd algorithm to calculate the minimum cost between any two nodes in
After the traversal ends, we return the answer.
The time complexity is
class Solution:
def minimumCost(
self,
source: str,
target: str,
original: List[str],
changed: List[str],
cost: List[int],
) -> int:
g = [[inf] * 26 for _ in range(26)]
for i in range(26):
g[i][i] = 0
for x, y, z in zip(original, changed, cost):
x = ord(x) - ord('a')
y = ord(y) - ord('a')
g[x][y] = min(g[x][y], z)
for k in range(26):
for i in range(26):
for j in range(26):
g[i][j] = min(g[i][j], g[i][k] + g[k][j])
ans = 0
for a, b in zip(source, target):
if a != b:
x, y = ord(a) - ord('a'), ord(b) - ord('a')
if g[x][y] >= inf:
return -1
ans += g[x][y]
return ansclass Solution {
public long minimumCost(
String source, String target, char[] original, char[] changed, int[] cost) {
final int inf = 1 << 29;
int[][] g = new int[26][26];
for (int i = 0; i < 26; ++i) {
Arrays.fill(g[i], inf);
g[i][i] = 0;
}
for (int i = 0; i < original.length; ++i) {
int x = original[i] - 'a';
int y = changed[i] - 'a';
int z = cost[i];
g[x][y] = Math.min(g[x][y], z);
}
for (int k = 0; k < 26; ++k) {
for (int i = 0; i < 26; ++i) {
for (int j = 0; j < 26; ++j) {
g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
}
}
}
long ans = 0;
int n = source.length();
for (int i = 0; i < n; ++i) {
int x = source.charAt(i) - 'a';
int y = target.charAt(i) - 'a';
if (x != y) {
if (g[x][y] >= inf) {
return -1;
}
ans += g[x][y];
}
}
return ans;
}
}class Solution {
public:
long long minimumCost(string source, string target, vector<char>& original, vector<char>& changed, vector<int>& cost) {
const int inf = 1 << 29;
int g[26][26];
for (int i = 0; i < 26; ++i) {
fill(begin(g[i]), end(g[i]), inf);
g[i][i] = 0;
}
for (int i = 0; i < original.size(); ++i) {
int x = original[i] - 'a';
int y = changed[i] - 'a';
int z = cost[i];
g[x][y] = min(g[x][y], z);
}
for (int k = 0; k < 26; ++k) {
for (int i = 0; i < 26; ++i) {
for (int j = 0; j < 26; ++j) {
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
}
}
long long ans = 0;
int n = source.length();
for (int i = 0; i < n; ++i) {
int x = source[i] - 'a';
int y = target[i] - 'a';
if (x != y) {
if (g[x][y] >= inf) {
return -1;
}
ans += g[x][y];
}
}
return ans;
}
};func minimumCost(source string, target string, original []byte, changed []byte, cost []int) (ans int64) {
const inf = 1 << 29
g := make([][]int, 26)
for i := range g {
g[i] = make([]int, 26)
for j := range g[i] {
if i == j {
g[i][j] = 0
} else {
g[i][j] = inf
}
}
}
for i := 0; i < len(original); i++ {
x := int(original[i] - 'a')
y := int(changed[i] - 'a')
z := cost[i]
g[x][y] = min(g[x][y], z)
}
for k := 0; k < 26; k++ {
for i := 0; i < 26; i++ {
for j := 0; j < 26; j++ {
g[i][j] = min(g[i][j], g[i][k]+g[k][j])
}
}
}
n := len(source)
for i := 0; i < n; i++ {
x := int(source[i] - 'a')
y := int(target[i] - 'a')
if x != y {
if g[x][y] >= inf {
return -1
}
ans += int64(g[x][y])
}
}
return
}function minimumCost(
source: string,
target: string,
original: string[],
changed: string[],
cost: number[],
): number {
const [n, m, MAX] = [source.length, original.length, Number.POSITIVE_INFINITY];
const g: number[][] = Array.from({ length: 26 }, () => Array(26).fill(MAX));
const getIndex = (ch: string) => ch.charCodeAt(0) - 'a'.charCodeAt(0);
for (let i = 0; i < 26; ++i) g[i][i] = 0;
for (let i = 0; i < m; ++i) {
const x = getIndex(original[i]);
const y = getIndex(changed[i]);
const z = cost[i];
g[x][y] = Math.min(g[x][y], z);
}
for (let k = 0; k < 26; ++k) {
for (let i = 0; i < 26; ++i) {
for (let j = 0; g[i][k] < MAX && j < 26; j++) {
if (g[k][j] < MAX) {
g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
}
}
}
}
let ans = 0;
for (let i = 0; i < n; ++i) {
const x = getIndex(source[i]);
const y = getIndex(target[i]);
if (x === y) continue;
if (g[x][y] === MAX) return -1;
ans += g[x][y];
}
return ans;
}/**
* @param {string} source
* @param {string} target
* @param {character[]} original
* @param {character[]} changed
* @param {number[]} cost
* @return {number}
*/
var minimumCost = function (source, target, original, changed, cost) {
const [n, m, MAX] = [source.length, original.length, Number.POSITIVE_INFINITY];
const g = Array.from({ length: 26 }, () => Array(26).fill(MAX));
const getIndex = ch => ch.charCodeAt(0) - 'a'.charCodeAt(0);
for (let i = 0; i < 26; ++i) g[i][i] = 0;
for (let i = 0; i < m; ++i) {
const x = getIndex(original[i]);
const y = getIndex(changed[i]);
const z = cost[i];
g[x][y] = Math.min(g[x][y], z);
}
for (let k = 0; k < 26; ++k) {
for (let i = 0; i < 26; ++i) {
for (let j = 0; g[i][k] < MAX && j < 26; j++) {
if (g[k][j] < MAX) {
g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
}
}
}
}
let ans = 0;
for (let i = 0; i < n; ++i) {
const x = getIndex(source[i]);
const y = getIndex(target[i]);
if (x === y) continue;
if (g[x][y] === MAX) return -1;
ans += g[x][y];
}
return ans;
};