Re: [閒聊] 每日leetcode
2976. Minimum Cost to Convert String I
## 思路
先用original, changed, cost三個array建立Graph
掃source/target字串時對每個字元做dijkstra
## Complexity
source = N
original = M
Time:
Space: O(M+N)
## Code
```python
class Solution:
def minimumCost(self, source: str, target: str, original: List[str],
changed: List[str], cost: List[int]) -> int:
graph = defaultdict(list)
for ori_ch, new_ch, c in zip(original, changed, cost):
graph[ori_ch].append((c, new_ch))
@cache
def get_min_cost(src, dst):
heap = [(0, src)]
seen = {src: 0}
while heap:
curr_cost, ch = heapq.heappop(heap)
if ch == dst:
return curr_cost
for next_cost, next_ch in graph[ch]:
if next_ch not in seen or seen[next_ch] > curr_cost +
next_cost:
seen[next_ch] = curr_cost + next_cost
heapq.heappush(heap, (curr_cost + next_cost, next_ch))
return -1
ans = 0
for src, dst in zip(source, target):
min_cost = get_min_cost(src, dst)
if min_cost == -1:
return -1
ans += min_cost
return ans
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.91 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722048005.A.169.html