⚡Flashcard Drill➔
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

  1. Each conversion is an edge between two letters, so there are only 26 nodes.
  2. Floyd-Warshall over the 26 letters gives the cheapest cost of converting any letter into any other, including via chains.
  3. Then sum the per-position costs, returning -1 if any pair is unreachable.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Advanced Graphs Problems