核心内容摘要
《时间静止！我！》：当校园日常被暂停，一场青春的奇遇悄然发生
【LetMeFly】
转换字符串的最小成本 Ifloyd算法(全源最短路)力扣题目链接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 105source、target均由小写英文字母组成1 cost.length original.length changed.length 2000original[i]、changed[i]是小写英文字母1 cost[i] 106original[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(intk0;k26;k){for(inti0;i26;i){for(intj0;j26;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^
O(len(original)len(original)C
其中C 16 C16C16空间复杂度O ( C 2 ) O(C^
O(C
AC代码C/* * LastEditTime:
12:22:44 */typedeflonglongll;classSolution{public:longlongminimumCost(string source,string target,vectorcharoriginal,vectorcharchanged,vectorintcost){ll floyd[26][26];memset(floyd,0x3f,sizeof(floyd));for(inti0;i26;i){floyd[i][i]0;}for(inti0;ioriginal.size();i){intxoriginal[i]-a;intychanged[i]-a;floyd[x][y]min(floyd[x][y],(ll)cost[i]);}for(intk0;k26;k){for(inti0;i26;i){for(intj0;j26;j){floyd[i][j]min(floyd[i][j],floyd[i][k]floyd[k][j]);}}}ll ans0;for(inti0;isource.size();i){ll costfloyd[source[i]-a][target[i]-a];if(cost
{return-1;}anscost;}returnans;}};对了邀请你看几个好看的hash8888a400009f000097还带签名的。
同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~千篇源码题解已开源