Problem: 100156. 转换字符串的最小成本 I

[TOC]

思路

python dijkstra

解题方法

python dijkstra

Code

###Python3

class Solution:
    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
        ans=0
        g=[[] for _ in range(26)]
        for i,j,c in zip(original,changed,cost):
            heappush(g[ord(i)-ord('a')],[c,ord(j)-ord('a')])
        d=defaultdict(int)
        def dijkstra(x,y):#dijkstra
            distant=0
            vis=set()
            q=[]
            q.append([0,x])
            while q:
                c,temp=heappop(q)
                if temp==y:
                    return c
                if temp in vis:
                    continue
                vis.add(temp)
                for cc,xx in g[temp]:
                    heappush(q,[c+cc,xx])
            return -1
        for i,j in zip(source,target):
            if i!=j:
                if (ord(i)-ord('a'),ord(j)-ord('a')) in d:
                    ans+=d[ord(i)-ord('a'),ord(j)-ord('a')]
                else :
                    res=dijkstra(ord(i)-ord('a'),ord(j)-ord('a'))
                    if res==-1:
                        return -1
                    ans+=res
                    d[ord(i)-ord('a'),ord(j)-ord('a')]=res
        return ans