品牌建设题目,志鸿优化设计,简单的网页制作模板,北京网络行业协会Leetcode 2976. Minimum Cost to Convert String I 1. 解题思路2. 代码实现 题目链接#xff1a;2976. Minimum Cost to Convert String I
1. 解题思路
这道题思路上其实是非常直接的#xff0c;本质上就是给出有向图之后#xff0c;求出有向图上任意两点之间的最短距离2976. Minimum Cost to Convert String I
1. 解题思路
这道题思路上其实是非常直接的本质上就是给出有向图之后求出有向图上任意两点之间的最短距离然后考察将source字符串转换为target字符串时所需要的cost。
因此难度上来说就是在给定一系列有向变换路径之后怎么求任意两个可行的变换之间的最小cost这个用Floyd算法就能够直接获得了有点类似Leetcode 2959之前也写过一个博客介绍过那道题的解答这里基本就直接复制之前的Floyd算法就行了。
2. 代码实现
给出python代码实现如下
class Solution:def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) - int:graph defaultdict(list)for u, v, c in zip(original, changed, cost):graph[u].append((v, c))costs [[0 if i j else math.inf for j in range(26)] for i in range(26)]for u, v, c in zip(original, changed, cost):u, v ord(u) - ord(a), ord(v) - ord(a)costs[u][v] min(costs[u][v], c)for k in range(26):for i in range(26):for j in range(26):costs[i][j] min(costs[i][k]costs[k][j], costs[i][j])ans 0for u, v in zip(source, target):u, v ord(u) - ord(a), ord(v) - ord(a)if costs[u][v] math.inf:return -1ans costs[u][v]return ans提交代码评测得到耗时1963ms占用内存19.1MB。
