NeetCode #641LC-2976MediumAdvanced Graphs
← Back to All Problems#641 · #2976 · Minimum Cost to Convert String I(转换字符串的最小成本 I)
📌 Problem Statement & Constraints
You are given
source, target, and parallel arrays original, changed, cost describing conversions between lowercase letters. Return the minimum cost to convert source into target, or -1. Constraints: 1 <= source.length <= 10^5, 0 <= original.length <= 2000, 1 <= cost[i] <= 10^6.💡 Core Algorithmic Approaches
- Each conversion is an edge between two letters, so there are only 26 nodes.
- Floyd-Warshall over the 26 letters gives the cheapest cost of converting any letter into any other, including via chains.
- Then sum the per-position costs, returning -1 if any pair is unreachable.
- The tiny graph makes the O(26^3) Floyd-Warshall essentially free.
💻 Benchmark Python3 Implementation
class Solution:
def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
INF = float("inf")
d = [[INF] * 26 for _ in range(26)]
for i in range(26):
d[i][i] = 0 # a letter converts to itself for free
for a, b, c in zip(original, changed, cost):
i, j = ord(a) - 97, ord(b) - 97
if c < d[i][j]:
d[i][j] = c # keep the cheapest direct conversion
# Floyd-Warshall over the 26 letters
for k in range(26):
for i in range(26):
if d[i][k] == INF:
continue
for j in range(26):
if d[i][k] + d[k][j] < d[i][j]:
d[i][j] = d[i][k] + d[k][j]
total = 0
for a, b in zip(source, target):
c = d[ord(a) - 97][ord(b) - 97]
if c == INF:
return -1 # impossible conversion
total += c
return total⚡ Complexity Deep Dive
⏱️ Time Complexity
O(26^3 + n) = O(n): the Floyd-Warshall is a constant, then one pass over the strings.
💾 Space Complexity
O(26^2) for the distance matrix.
⚠️ Interview Pitfalls & Follow-ups
- Running Dijkstra per position: O(n * E log V); the 26-node closure makes it O(n).
- Forgetting the diagonal: a letter must be able to stay unchanged.
- Not keeping the cheapest parallel conversion: duplicate pairs may have different costs.
- Returning a partial sum for an impossible conversion: the answer must be -1.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.