Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

3235. Minimum Cost to Convert String I

My accepted Python solution to LeetCode problem 3235, Minimum Cost to Convert String I, running in 755ms.

  • Difficulty: Medium
  • Python
  • Runtime 755ms
  • Memory 18.7MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 755ms, memory 18.7MB, accepted 2026-01-01.

python
class Solution:
    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
        # Build graph with minimum costs using Floyd-Warshall
        INF = float('inf')
        dist = [[INF] * 26 for _ in range(26)]
        
        # Distance to self is 0
        for i in range(26):
            dist[i][i] = 0
        
        # Add edges from original to changed with cost
        for o, c, co in zip(original, changed, cost):
            u = ord(o) - ord('a')
            v = ord(c) - ord('a')
            dist[u][v] = min(dist[u][v], co)
        
        # Floyd-Warshall algorithm
        for k in range(26):
            for i in range(26):
                for j in range(26):
                    if dist[i][k] + dist[k][j] < dist[i][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
        
        # Calculate total cost
        total = 0
        for s, t in zip(source, target):
            u = ord(s) - ord('a')
            v = ord(t) - ord('a')
            if dist[u][v] == INF:
                return -1
            total += dist[u][v]
        
        return total

Source