🎠 2976.转换字符串的最小成本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
思路
基本思想
题目中说会给出一部分的字符之间的转换成本，根据这些字符的转换成本得到将source转换成target的最小成本，针对source和target的每个对应位置上的字符来说，都是求这两个字符之间的最小距离，因为字符之间转换的关系可以用一个图表示出来，图中的边就是转换成本，针对每一个要从source转换到target的字符，求出其最短路径即可，这就是图的最短路径问题
首先要建立一个邻接矩阵，并更新出当前字符的一步转换成本，也就是：
1
2
3
4
5
6
7
8
9
10
11
| int[][] dist=new int[26][26];
for(int i=0;i<26;++i){
Arrays.fill(dist[i],Integer.MAX_VALUE/2);
dist[i][i]=0;
}
//统计一步变化距离
for(int i=0;i<original.length;++i){
int begin=original[i]-'a';
int end=changed[i]-'a';
dist[begin][end]=Math.min(dist[begin][end],cost[i]);
}
|
然后利用弗洛伊德算法求出任意两点之间的最短距离，之后遍历source和target的对应位置，需要转换就从更新完毕的邻接矩阵dist中找到最短距离即可
弗洛伊德更新代码为：
1
2
3
4
5
6
7
| for(int k=0;k<26;++k){
for(int i=0;i<26;++i){
for(int j=0;j<26;++j){
dist[i][j]=Math.min(dist[i][j],dist[i][k]+dist[k][j]);
}
}
}
|
需要注意几个点：
- 初始化时要注意到自身的成本为0
- 到不可达的节点成本为
Integer.MAX_VALUE/2，不是Integer.MAX_VALUE，也不是1000001，使用Integer.MAX_VALUE会造成弗洛伊德算法更新时溢出，使用1000001时会造成如果当前cost[i]刚好累加到了1000001，那么会认为这两个顶点不可达 - 使用字符一步转换的矩阵cost构造出邻接矩阵之后，才开始执行弗洛伊德算法
执行流程
- 初始化邻接矩阵，不可达节点间的成本为
Integer.MAX_VALUE/2，到自身的成本为0 - 根据成本转换矩阵构造两点之间的一步成本
- 根据弗洛伊德算法更新两点之间的最短距离
- 计算source到target每个字符的转换成本并累加
- 统计的途中有两个字符之间无法转换（不可达），此时返回-1
- 统计完成返回最终的结果
代码
根据以上分析，得出以下代码：
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
| class Solution {
//全是细节
//看这些字符转换的最短路径（图的最短路径问题）
public long minimumCost(String source, String target, char[] original, char[] changed, int[] cost) {
//更新初始邻接矩阵
int[][] dist=new int[26][26];
for(int i=0;i<26;++i){
Arrays.fill(dist[i],Integer.MAX_VALUE/2);
dist[i][i]=0;
}
//统计一步变化距离
for(int i=0;i<original.length;++i){
int begin=original[i]-'a';
int end=changed[i]-'a';
dist[begin][end]=Math.min(dist[begin][end],cost[i]);
}
//弗洛伊德算法求出每个字符到其余字符的最短变化距离
for(int k=0;k<26;++k){
for(int i=0;i<26;++i){
for(int j=0;j<26;++j){
dist[i][j]=Math.min(dist[i][j],dist[i][k]+dist[k][j]);
}
}
}
//要更新字符之间的直接变化次数
//防止溢出
long res=0;
for(int i=0;i<source.length();++i){
//当前两个元素压根无法转换
if(dist[source.charAt(i)-'a'][target.charAt(i)-'a']==Integer.MAX_VALUE/2){
return -1;
}
//可以转换，记录最短距离
res+=dist[source.charAt(i)-'a'][target.charAt(i)-'a'];
}
return res;
}
}
|
总结
主要是利用弗洛伊德求出图中任意两点的最短距离，前提是要构造好邻接矩阵，注意不可达的两点之间要使用Integer.MAX_VALUE/2表示