从Leetcode 每日一题练习继续讨论:
2976. 转换字符串的最小成本 I
2976. Minimum Cost to Convert String I
题解
本题和昨天的题目核心思路上基本相同, 只需要遍历原始字母和其映射字母以及相应的花费, 将字母对应的映射字母和其花费保存起来, 这里可以使用一个map, 也可以把字母当成下标, 用一个26*26的数组来保存(只有小写字母). 关键还是当原始字母和映射字母均相同时如果有多个不同的花费, 要将最小的花费保存下来. 因为这里我们只关心最小花费, 每个映射都是最小花费最终得到的即为最小花费, 是一个比较清晰的贪心法. 需要注意的是可能存在c->e, e->b这样的转换的花费比c->b小得多, 是不是感觉很熟悉, 实际上这个问题完全可以把字母当成节点, 花费当成边的花费, 这样问题就转换成了和昨天完全一样的问题. 使用同样的方法求解即可. 本题中求解最短路径我们使用Floyd-Warshall算法, 该算法的原理为动态规划.
代码
func minimumCost(source string, target string, original []byte, changed []byte, cost []int) int64 {
costs := make([][]int, 26)
for i,_ := range costs{
costs[i] = make([]int, 26)
for j:= range costs[i]{
costs[i][j] = math.MaxInt32
}
costs[i][i] = 0
}
for i,_ := range original{
costs[original[i]-'a'][changed[i]-'a'] = min(cost[i],costs[original[i]-'a'][changed[i]-'a'])
}
for k:=0;k<26;k++{
for i:=0;i<26;i++{
for j:=0;j<26;j++{
if costs[i][j] > costs[i][k]+costs[k][j] {
costs[i][j] = costs[i][k] + costs[k][j]
}
}
}
}
result := 0
for i := range source{
if costs[source[i]-'a'][target[i]-'a'] == math.MaxInt32{
return -1
}else{
result += costs[source[i]-'a'][target[i]-'a']
}
}
return int64(result)
}
总结
如果点特别多并且图为稀疏图, 用map来保存边的权重并执行Floyd算法效率会更高, 避免了不连通的边的遍历.