Problem: 2976. 转换字符串的最小成本 I
文章目录
- 整体思路
- 1. 核心问题
- 2. 算法与逻辑步骤
- 完整代码
- 时空复杂度
整体思路
1. 核心问题
我们需要将source字符串转换为target字符串。转换规则由original,changed,cost数组给出，表示将字符original[i]变为changed[i]需要花费cost[i]。
转换具有传递性（例如a -> b -> c），我们需要求出总的最小成本。如果无法转换，返回 -1。
2. 算法与逻辑步骤
这是一个典型的多源最短路径问题。
图的建模：
- 将 26 个小写英文字母看作图中的 26 个节点（‘a’ 对应 0，…，‘z’ 对应 25）。
- 输入的转换规则即为图中的有向边，权重为转换成本。
- 我们需要计算任意两个字符之间的最小转换代价。
Floyd-Warshall 算法：
- 由于节点数固定且非常少（仅 26 个），Floyd-Warshall 算法是解决此问题的最佳选择。它可以一次性计算出所有节点对之间的最短路径。
- 初始化：创建一个26 × 26 26 \times 2626×26的矩阵
minCosts。- 对角线（自己转自己）设为 0。
- 其他位置初始化为无穷大（这里用
Integer.MAX_VALUE / 2防止加法溢出）。 - 根据输入的边 (
original,changed,cost) 更新矩阵。注意可能有重边（多条规则描述同一种转换），取最小值。
- 三重循环松弛：通过中间节点
k，尝试优化从i到j的路径：minCosts[i][j] = min(minCosts[i][j], minCosts[i][k] + minCosts[k][j])。
计算总成本：
- 预处理完成后，我们拥有了一个查找表
minCosts，可以在O ( 1 ) O(1)O(1)时间内查询任意字符转换的最优代价。 - 遍历
source和target字符串，逐个字符查询转换成本并累加。 - 如果在任意位置查询到的成本为无穷大（
UNREACHABLE），说明不可达，立即返回 -1。
- 预处理完成后，我们拥有了一个查找表
完整代码
importjava.util.Arrays;classSolution{publiclongminimumCost(Stringsource,Stringtarget,char[]original,char[]changed,int[]cost){// 定义一个足够大的数表示不可达，但不能是 Integer.MAX_VALUE，否则相加会溢出finalintUNREACHABLE=Integer.MAX_VALUE/2;// 字母表大小，固定为 26finalintALPHABET_SIZE=26;// minCosts[i][j] 存储从字符 i 转换到字符 j 的最小成本int[][]minCosts=newint[ALPHABET_SIZE][ALPHABET_SIZE];// 1. 初始化距离矩阵for(inti=0;i<ALPHABET_SIZE;i++){// 默认所有转换都不可达Arrays.fill(minCosts[i],UNREACHABLE);// 字符转换为自身的成本为 0minCosts[i][i]=0;}// 2. 根据输入构建初始图for(inti=0;i<cost.length;i++){intfromIndex=original[i]-'a';inttoIndex=changed[i]-'a';// 注意：输入中可能存在多条相同起止点的边，必须取最小值minCosts[fromIndex][toIndex]=Math.min(minCosts[fromIndex][toIndex],cost[i]);}// 3. 使用 Floyd-Warshall 算法计算所有节点对的最短路径// k 是中间节点for(intk=0;k<ALPHABET_SIZE;k++){// i 是起始节点for(inti=0;i<ALPHABET_SIZE;i++){// 剪枝：如果起点到中间点不可达，就没必要继续看了if(minCosts[i][k]==UNREACHABLE){continue;}// j 是终点for(intj=0;j<ALPHABET_SIZE;j++){// 状态转移：比较 "直接从 i 到 j" 和 "经由 k 从 i 到 j" 的成本if(minCosts[k][j]!=UNREACHABLE){minCosts[i][j]=Math.min(minCosts[i][j],minCosts[i][k]+minCosts[k][j]);}}}}// 4. 计算 source 转换到 target 的总成本longtotalCost=0;// 使用 long 防止总成本溢出 int 范围intlen=source.length();for(inti=0;i<len;i++){intsourceCharIdx=source.charAt(i)-'a';inttargetCharIdx=target.charAt(i)-'a';// 查表获取最小转换成本intcurrentPairCost=minCosts[sourceCharIdx][targetCharIdx];// 如果某个字符无法转换，说明整个任务失败if(currentPairCost==UNREACHABLE){return-1;}totalCost+=currentPairCost;}returntotalCost;}}时空复杂度
假设source的长度为N NN，转换规则数组（边）的长度为M MM，字符集大小为C CC（本题中C = 26 C=26C=26）。
1. 时间复杂度：O ( N + M + C 3 ) O(N + M + C^3)O(N+M+C3)
- 初始化图：遍历M MM条边，耗时O ( M ) O(M)O(M)。
- Floyd-Warshall 算法：包含三重循环，每重循环次数为C CC，耗时O ( C 3 ) O(C^3)O(C3)。由于C = 26 C=26C=26，这是一个非常小的常数（26 3 ≈ 1.7 × 10 4 26^3 \approx 1.7 \times 10^4263≈1.7×104）。
- 计算总成本：遍历长度为N NN的字符串，每次查表O ( 1 ) O(1)O(1)，耗时O ( N ) O(N)O(N)。
- 总计：O ( N + M + C 3 ) O(N + M + C^3)O(N+M+C3)。在实际应用中，N NN通常是主导项。
2. 空间复杂度：O ( C 2 ) O(C^2)O(C2)
- 距离矩阵：我们需要一个C × C C \times CC×C的二维数组
minCosts来存储最短路径。 - 结论：O ( C 2 ) O(C^2)O(C2)，对于C = 26 C=26C=26，空间消耗极小且固定。
