LeetCode 2976 Minimum Cost to Convert String I

Minimum Cost to Convert String I

Problem Description

You are given two 0-indexed strings, source and target, both of length n and consisting of lowercase English letters. You are also provided with two 0-indexed character arrays, original and changed, and an integer array cost, where cost[i] represents the cost of changing the character original[i] to the character changed[i].

The goal is to convert the source string into the target string using the fewest operations possible. Each operation involves changing a character x in source to a character y if a conversion path exists from x to y at a specified cost. If it is impossible to convert source to target, the function should return -1.

Constraints

• 1 <= source.length == target.length <= 10^5
• source and target consist of lowercase English letters.
• 1 <= cost.length == original.length == changed.length <= 2000
• original[i], changed[i] are lowercase English letters.
• 1 <= cost[i] <= 10^6
• original[i] != changed[i]

Example

Example 1

• Input:

  source = "abcd"
  target = "acbe"
  original = ["a", "b", "c", "c", "e", "d"]
  changed = ["b", "c", "b", "e", "b", "e"]
  cost = [2, 5, 5, 1, 2, 20]
  

• Output: 28
• Explanation:
  • Change ‘b’ to ‘c’ at a cost of 5.
  • Change ‘c’ to ‘e’ at a cost of 1.
  • Change ‘e’ to ‘b’ at a cost of 2.
  • Change ‘d’ to ‘e’ at a cost of 20.
  • Total cost = 5 + 1 + 2 + 20 = 28.

Example 2

• Input:

  source = "aaaa"
  target = "bbbb"
  original = ["a", "c"]
  changed = ["c", "b"]
  cost = [1, 2]
  

• Output: 12
• Explanation:
  • Change ‘a’ to ‘c’ at a cost of 1, then ‘c’ to ‘b’ at a cost of 2.
  • Total cost for all occurrences of ‘a’ to ‘b’ = (1 + 2) * 4 = 12.

Example 3

• Input:

  source = "abcd"
  target = "abce"
  original = ["a"]
  changed = ["e"]
  cost = [10000]
  

• Output: -1
• Explanation:
  • It is impossible to convert ‘d’ to ‘e’ with the given operations.

Solution

The solution involves representing each character transformation as a graph edge with associated costs, and using the Floyd-Warshall algorithm to find the shortest path (minimum cost) to convert each character in source to the corresponding character in target.

Python Implementation

class Solution(object):
    def minimumCost(self, source, target, original, changed, cost):
        """
        :type source: str
        :type target: str
        :type original: List[str]
        :type changed: List[str]
        :type cost: List[int]
        :rtype: int
        """
        # Function to convert character to index
        def char_to_index(c):
            return ord(c) - ord('a')
        
        # Initialize the distance matrix with infinity
        inf = float('inf')
        dist = [[inf] * 26 for _ in range(26)]
        
        # Set the distance from each character to itself to zero
        for i in range(26):
            dist[i][i] = 0
        
        # Fill the distance matrix with given conversion costs
        for o, c, z in zip(original, changed, cost):
            o_index = char_to_index(o)
            c_index = char_to_index(c)
            dist[o_index][c_index] = min(dist[o_index][c_index], z)
        
        # Apply Floyd-Warshall algorithm to find shortest paths between all pairs of nodes
        for k in range(26):
            for i in range(26):
                for j in range(26):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
        
        # Calculate the total minimum cost to convert source to target
        total_cost = 0
        for s_char, t_char in zip(source, target):
            if s_char == t_char:
                continue
            s_index = char_to_index(s_char)
            t_index = char_to_index(t_char)
            
            # If there's no path from source character to target character, return -1
            if dist[s_index][t_index] == inf:
                return -1
            
            total_cost += dist[s_index][t_index]
        
        return total_cost

Explanation

1. Character Index Mapping: Each character is mapped to an index using ord(c) - ord('a') to facilitate matrix operations.

2. Distance Matrix Initialization: A 2D matrix dist is initialized with inf values, except for the diagonal which is set to 0 (cost of converting a character to itself).

3. Populate Distance Matrix: Using the original, changed, and cost arrays, populate the dist matrix with the minimum costs for direct conversions.

4. Floyd-Warshall Algorithm: This algorithm is applied to compute the shortest paths between all pairs of characters, taking into account possible intermediary conversions.

5. Calculate Total Cost: Iterate over source and target, summing the minimum conversion costs. If a character in source cannot be converted to the corresponding character in target, return -1.

6. Return Result: The total minimum cost is returned, or -1 if the conversion is impossible.