A.每日一题——2976. 转换字符串的最小成本 I

题目链接：2976. 转换字符串的最小成本 I（中等）

算法原理：

解法：图论 + Floyd-Warshall（弗洛伊德）

13ms击败91.30%

时间复杂度O(n+m+∣Σ∣³)，其中 n 为 source 的长度，m 为 cost 的长度，∣Σ∣ 为字符集合的大小，本题中字符均为小写字母，所以 ∣Σ∣=26

核心思想：字符转换问题转化为「多源最短路径问题」

①把 26 个小写字母视为图的 26 个节点
②字符 A 转字符 B 的成本视为节点 A 到 B 的有向边权重
③求 “source 转 target 的最小总成本” 等价于 “依次求每个对应字符对的最短路径，再累加”

具体步骤：

1.问题建模
①定义 26×26 的距离矩阵dis，dis[i][j]表示字符'a'+i转换为'a'+j的最小成本
②矩阵初始化：dis[i][i] = 0，自身转自身成本为 0，其余值设为极大值INF，表示初始不可达
2.填充直接转换成本
①遍历original、changed、cost数组，将字符转换为对应索引（c-'a'）
②若存在字符x转y的直接成本，为处理重复转化的情况，更新dis[x][y]为 “当前值” 和 “给定成本” 的最小值
3.Floyd-Warshall 求全源最短路径
①三层循环（中间节点 k → 源节点 i → 目标节点 j），核心公式：
②dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
③剪枝优化：若i 到 k 不可达：dis[i][k] = INF，则直接跳过
4.计算总转换成本
①遍历source和target的每个对应字符，取其索引s和t
②若该字符转换不可达：dis[s][t] = INF，直接返回 - 1
③否则累加dis[s][t]，最终返回累加结果（用 long 类型避免 int 溢出）

Java代码：

class Solution { public long minimumCost(String source, String target, char[] original, char[] changed, int[] cost) { //定义为最大值的一半，防止后续相加溢出 final int INF=0x3f3f3f3f; //dis[i][j]:i处字符转化为j处字符的最小成本 int[][] dis=new int[26][26]; //初始化为INF，表示初始不可达 for(int i=0;i<26;i++){ Arrays.fill(dis[i],INF); dis[i][i]=0;//字符自身转为自身，成本为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]); } //求任意两个字符间的最短路i->k->j //i:源字符,k:中间转换字符,j:目标字符 for(int k=0;k<26;k++){ for(int i=0;i<26;i++){ //剪枝优化，若i->k不可达，无需计算i->k->j的路径 if(dis[i][k]==INF) continue; for(int j=0;j<26;j++) dis[i][j]=Math.min(dis[i][j],dis[i][k]+dis[k][j]); } } //计算source转target的总最小成本，用long避免int溢出 long ret=0; for(int i=0;i<source.length();i++){ //取出索引 int s=source.charAt(i)-'a'; int t=target.charAt(i)-'a'; //若当前字符转换不可达，直接返回-1 if(dis[s][t]==INF) return -1; ret+=dis[s][t]; } return ret; } }