转换字符串的最小成本 I
难度:
标签:
题目描述
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]
代码结果
运行时间: 304 ms, 内存: 17.9 MB
/*
* This solution involves creating a map of transformations and costs, and then
* using dynamic programming with Java Streams to find the minimum cost to transform
* the source string into the target string. If a transformation is impossible, it returns -1.
*/
import java.util.*;
import java.util.stream.*;
public class MinCostTransformationStream {
public int minCost(String source, String target, char[] original, char[] changed, int[] cost) {
int n = source.length();
Map<Character, Map<Character, Integer>> transCost = IntStream.range(0, original.length).boxed()
.collect(Collectors.toMap(
i -> original[i],
i -> new HashMap<>(Map.of(changed[i], cost[i])),
(map1, map2) -> {
map1.putAll(map2);
return map1;
}
));
return IntStream.range(0, n).map(i -> {
char srcChar = source.charAt(i);
char tgtChar = target.charAt(i);
if (srcChar == tgtChar) return 0;
if (!transCost.containsKey(srcChar)) return -1;
Queue<Character> queue = new LinkedList<>();
Map<Character, Integer> minCost = new HashMap<>();
queue.offer(srcChar);
minCost.put(srcChar, 0);
boolean[] found = {false};
while (!queue.isEmpty() && !found[0]) {
char curr = queue.poll();
int currCost = minCost.get(curr);
if (curr == tgtChar) {
found[0] = true;
return currCost;
}
if (!transCost.containsKey(curr)) continue;
transCost.get(curr).forEach((nextChar, nextCost) -> {
int newCost = currCost + nextCost;
if (!minCost.containsKey(nextChar) || newCost < minCost.get(nextChar)) {
minCost.put(nextChar, newCost);
queue.offer(nextChar);
}
});
}
return found[0] ? minCost.getOrDefault(tgtChar, -1) : -1;
}).reduce(0, (a, b) -> a == -1 || b == -1 ? -1 : a + b);
}
public static void main(String[] args) {
MinCostTransformationStream solution = new MinCostTransformationStream();
String source = "abcd";
String target = "acbe";
char[] original = {'a', 'b', 'c', 'c', 'e', 'd'};
char[] changed = {'b', 'c', 'b', 'e', 'b', 'e'};
int[] cost = {2, 5, 5, 1, 2, 20};
System.out.println(solution.minCost(source, target, original, changed, cost)); // Output: 28
}
}
解释
方法:
题解使用了图的最短路径算法（Floyd-Warshall 变体）来计算字符转换的最小成本。首先，建立一个 26x26 的矩阵 mat，用于表示从一个字符到另一个字符的最小转换成本。矩阵中每个元素初始化为无穷大，除了对角线元素（即自身到自身的转换成本为0）。随后，使用一个数组 map0 来存储每个字符对的最小转换成本。接着使用一个深度优先搜索（DFS）结合优先队列（最小堆）来计算任何字符到任何字符的最短路径。最后，遍历 source 字符串和 target 字符串，利用预计算的最短路径成本矩阵来计算整体的最小转换成本。如果任何字符的转换成本为无穷大，表明转换不可能完成，返回 -1。
时间复杂度:
O(k + 26^2 * log(26) + n)
空间复杂度:
O(k + 26^2)
代码细节讲解
🦆
为什么在处理字符转换成本时选择使用图的最短路径算法，特别是Floyd-Warshall变体？
▷🦆
在建立字符到字符的成本映射时，如何处理存在多个不同成本的相同字符转换规则（例如多个original到changed的转换规则）？
▷🦆
DFS和最小堆结合使用的主要目的是什么，它的工作原理是如何实现的？
▷🦆
在DFS中使用优先队列（最小堆）时，为什么需要检查出队元素的成本是否与当前矩阵中记录的成本一致？
▷