当前位置：首页 > news >正文

LeetCode 2976.转换字符串的最小成本 I：floyd算法(全源最短路)

news 2026/5/11 22:57:37

【LetMeFly】2976.转换字符串的最小成本 I：floyd算法(全源最短路)

力扣题目链接：https://leetcode.cn/problems/minimum-cost-to-convert-string-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 <= 10⁵
source、target均由小写英文字母组成
1 <= cost.length== original.length == changed.length <= 2000
original[i]、changed[i]是小写英文字母
1 <= cost[i] <= 10⁶
original[i] != changed[i]

解题方法：floyd算法

如何将source字符串变为target字符串？必须一个字符一个字符地通过cost[i]的代价将original[i]变为changed[i]来实现。

不难发现source中每个字符是独立的，并且从一个字符a aa经过数次变化最终变为字符b bb的最小代价也是固定的，所以我们不妨先计算出26 × 26 26\times 2626×26种字母的转换方式分别最少需要花费多少代价：

将26个字母看成图中26个顶点，
假设通过cost[i]的代价可以将original[i]变为changed[i]，那么就看作有一个从节点original[i]指向节点changed[i]且代价为cost[i]的边。
floyd算法最适合算这个了，初始化floyd[i][i]=0，有直接a指向b的边的初始化floyd[a][b]为a指向b中代价最小的边，其他初始化为正无穷。然后：
for(intk=0;k<26;k++){for(inti=0;i<26;i++){for(intj=0;j<26;j++){floyd[i][j]=min(floyd[i][j],floyd[i][k]+floyd[k][j]);}}}
就计算出任何一个字母转为另一个字母的最小代价了。

对original字符串中每个字母做最小代价转换，累加并返回答案或-1即可。

时间复杂度O ( l e n ( o r i g i n a l ) + l e n ( o r i g i n a l ) + C 2 ) O(len(original)+len(original)+C^2)O(len(original)+len(original)+C2)，其中C = 16 C=16C=16
空间复杂度O ( C 2 ) O(C^2)O(C2)

AC代码

C++

/* * @LastEditTime: 2026-01-31 12:22:44 */typedeflonglongll;classSolution{public:longlongminimumCost(string source,string target,vector<char>&original,vector<char>&changed,vector<int>&cost){ll floyd[26][26];memset(floyd,0x3f,sizeof(floyd));for(inti=0;i<26;i++){floyd[i][i]=0;}for(inti=0;i<original.size();i++){intx=original[i]-'a';inty=changed[i]-'a';floyd[x][y]=min(floyd[x][y],(ll)cost[i]);}for(intk=0;k<26;k++){for(inti=0;i<26;i++){for(intj=0;j<26;j++){floyd[i][j]=min(floyd[i][j],floyd[i][k]+floyd[k][j]);}}}ll ans=0;for(inti=0;i<source.size();i++){ll cost=floyd[source[i]-'a'][target[i]-'a'];if(cost>1000000000000){return-1;}ans+=cost;}returnans;}};