class Solution {
public:
long long minimumCost(string source, string target, vector<char>& original, vector<char>& changed, vector<int>& cost) {
}
};
100156. 转换字符串的最小成本 I
给你两个下标从 0 开始的字符串 source 和 target ，它们的长度均为 n 并且由 小写 英文字母组成。
另给你两个下标从 0 开始的字符数组 original 和 changed ，以及一个整数数组 cost ，其中 cost[i] 代表将字符 original[i] 更改为字符 changed[i] 的成本。
你从字符串 source 开始。在一次操作中，如果 存在 任意 下标 j 满足 cost[j] == z 、original[j] == x 以及 changed[j] == y 。你就可以选择字符串中的一个字符 x 并以 z 的成本将其更改为字符 y 。
返回将字符串 source 转换为字符串 target 所需的 最小 成本。如果不可能完成转换，则返回 -1 。
注意，可能存在下标 i 、j 使得 original[j] == original[i] 且 changed[j] == changed[i] 。
示例 1：
输入：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] 输出：28 解释：将字符串 "abcd" 转换为字符串 "acbe" ： - 更改下标 1 处的值 'b' 为 'c' ，成本为 5 。 - 更改下标 2 处的值 'c' 为 'e' ，成本为 1 。 - 更改下标 2 处的值 'e' 为 'b' ，成本为 2 。 - 更改下标 3 处的值 'd' 为 'e' ，成本为 20 。 产生的总成本是 5 + 1 + 2 + 20 = 28 。 可以证明这是可能的最小成本。
示例 2：
输入：source = "aaaa", target = "bbbb", original = ["a","c"], changed = ["c","b"], cost = [1,2] 输出：12 解释：要将字符 'a' 更改为 'b'： - 将字符 'a' 更改为 'c'，成本为 1 - 将字符 'c' 更改为 'b'，成本为 2 产生的总成本是 1 + 2 = 3。 将所有 'a' 更改为 'b'，产生的总成本是 3 * 4 = 12 。
示例 3：
输入：source = "abcd", target = "abce", original = ["a"], changed = ["e"], cost = [10000] 输出：-1 解释：无法将 source 字符串转换为 target 字符串，因为下标 3 处的值无法从 'd' 更改为 'e' 。
提示：
1 <= source.length == target.length <= 105source、target 均由小写英文字母组成1 <= cost.length== original.length == changed.length <= 2000original[i]、changed[i] 是小写英文字母1 <= cost[i] <= 106original[i] != changed[i]原站题解
golang 解法, 执行用时: 48 ms, 内存消耗: 7.4 MB, 提交时间: 2023-12-24 19:56:13
func minimumCost(source, target string, original, changed []byte, cost []int) (ans int64) {
dis := [26][26]int{}
for i := range dis {
for j := range dis[i] {
if j != i {
dis[i][j] = 1e13
}
}
}
for i, c := range cost {
x := original[i] - 'a'
y := changed[i] - 'a'
dis[x][y] = min(dis[x][y], c)
}
for k := range dis {
for i := range dis {
for j := range dis {
dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j])
}
}
}
for i, b := range source {
ans += int64(dis[b-'a'][target[i]-'a'])
}
if ans >= 1e13 {
return -1
}
return
}
java 解法, 执行用时: 22 ms, 内存消耗: 44.5 MB, 提交时间: 2023-12-24 19:55:59
class Solution {
public long minimumCost(String source, String target, char[] original, char[] changed, int[] cost) {
int[][] dis = new int[26][26];
for (int i = 0; i < 26; i++) {
Arrays.fill(dis[i], Integer.MAX_VALUE / 2);
dis[i][i] = 0;
}
for (int i = 0; i < cost.length; i++) {
int x = original[i] - 'a';
int y = changed[i] - 'a';
dis[x][y] = Math.min(dis[x][y], cost[i]);
}
for (int k = 0; k < 26; k++) {
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
dis[i][j] = Math.min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
long ans = 0;
for (int i = 0; i < source.length(); i++) {
int d = dis[source.charAt(i) - 'a'][target.charAt(i) - 'a'];
if (d == Integer.MAX_VALUE / 2) {
return -1;
}
ans += d;
}
return ans;
}
}
cpp 解法, 执行用时: 224 ms, 内存消耗: 85.7 MB, 提交时间: 2023-12-24 19:55:47
class Solution {
public:
long long minimumCost(string source, string target, vector<char> &original, vector<char> &changed, vector<int> &cost) {
int dis[26][26];
memset(dis, 0x3f, sizeof(dis));
for (int i = 0; i < 26; i++) {
dis[i][i] = 0;
}
for (int i = 0; i < cost.size(); i++) {
int x = original[i] - 'a';
int y = changed[i] - 'a';
dis[x][y] = min(dis[x][y], cost[i]);
}
for (int k = 0; k < 26; k++) {
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
long long ans = 0;
for (int i = 0; i < source.length(); i++) {
int d = dis[source[i] - 'a'][target[i] - 'a'];
if (d == 0x3f3f3f3f) {
return -1;
}
ans += d;
}
return ans;
}
};
python3 解法, 执行用时: 1820 ms, 内存消耗: 18.3 MB, 提交时间: 2023-12-24 19:55:35
'''
建图，从 original[i] 向 changed[i] 连边，边权为 cost[i]。
然后用 Floyd 算法求图中任意两点最短路，得到 dis 矩阵，
dis[i][j] 表示字母 i 通过若干次替换操作变成字母 j 的最小成本。
最后累加所有 dis[original[i]][changed[i]]，即为答案。如果答案为无穷大，返回 −1。
'''
class Solution:
def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
dis = [[inf] * 26 for _ in range(26)]
for i in range(26):
dis[i][i] = 0
for x, y, c in zip(original, changed, cost):
x = ord(x) - ord('a')
y = ord(y) - ord('a')
dis[x][y] = min(dis[x][y], c)
for k in range(26):
for i in range(26):
for j in range(26):
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
ans = sum(dis[ord(x) - ord('a')][ord(y) - ord('a')] for x, y in zip(source, target))
return ans if ans < inf else -1