Problem of The Day: Minimum Cost to Convert String I
Problem Statement
Intuition
To solve this problem, my initial thought is to use Dijkstra’s algorithm to find the shortest path between each pair of characters from ‘a’ to ‘z’. This will allow me to determine the minimum cost to convert any character in the source string to the corresponding character in the target string. By constructing a graph where the nodes represent characters and the edges represent the conversion costs, I can efficiently compute the minimum conversion cost using a shortest path algorithm.
Approach
First, I’ll create a graph where each node represents a character from ‘a’ to ‘z’, and the edges represent the cost to convert one character to another. I’ll then use Dijkstra’s algorithm to compute the shortest path between each pair of characters. This will result in a matrix where shortest_path_matrix[i][j] contains the minimum cost to convert character i to character j.
Once I have this matrix, I can iterate through each character in the source string and find the corresponding character in the target string. If the characters are different, I’ll use the shortest path matrix to determine the conversion cost and accumulate the total cost. If there’s no possible conversion (indicated by an infinite cost), I’ll return -1.
Complexity
-
Time complexity: The time complexity of this approach is (O(N^2 \log N + M \log M)), where (N) is the number of characters (26) and (M) is the number of conversion rules. The (N^2 \log N) term comes from running Dijkstra’s algorithm (N) times on a graph with (N) nodes. The (M \log M) term accounts for inserting the conversion rules into the priority queue in Dijkstra’s algorithm.
-
Space complexity: The space complexity is (O(N^2)), which is used for storing the shortest path matrix.
Code
import heapq
from typing import List
class Solution:
def dijkstra(self, graph, src, shortest_path_matrix, n):
queue = [(0, src)]
shortest_path_matrix[:] = [float('inf')] * n
shortest_path_matrix[src] = 0
while queue:
cost, node = heapq.heappop(queue)
if cost > shortest_path_matrix[node]:
continue
for next_node, next_cost in graph[node]:
if shortest_path_matrix[next_node] > cost + next_cost:
shortest_path_matrix[next_node] = cost + next_cost
heapq.heappush(queue, (shortest_path_matrix[next_node], next_node))
def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
if len(source) != len(target):
return -1
N = 26
graph = [[] for _ in range(N)]
shortest_path_matrix = [[float('inf')] * N for _ in range(N)]
for i in range(N):
shortest_path_matrix[i][i] = 0
for i in range(len(cost)):
src_idx = ord(original[i]) - ord('a')
dst_idx = ord(changed[i]) - ord('a')
c = cost[i]
graph[src_idx].append((dst_idx, c))
for i in range(N):
self.dijkstra(graph, i, shortest_path_matrix[i], N)
total_cost = 0
for i in range(min(len(source), len(target))):
if source[i] != target[i]:
row = ord(source[i]) - ord('a')
col = ord(target[i]) - ord('a')
if shortest_path_matrix[row][col] == float('inf'):
return -1
total_cost += shortest_path_matrix[row][col]
return total_cost
Editorial
Approach 1: Dijkstra’s Algorithm
class Solution:
def minimumCost(
self,
source: str,
target: str,
original: List[str],
changed: List[str],
cost: List[int],
) -> int:
# Create a graph representation of character conversions
adjacency_list = [[] for _ in range(26)]
# Populate the adjacency list with character conversions
conversion_count = len(original)
for i in range(conversion_count):
adjacency_list[ord(original[i]) - ord("a")].append(
(ord(changed[i]) - ord("a"), cost[i])
)
# Calculate shortest paths for all possible character conversions
min_conversion_costs = [
self._dijkstra(i, adjacency_list) for i in range(26)
]
# Calculate the total cost of converting source to target
total_cost = 0
for s, t in zip(source, target):
if s != t:
char_conversion_cost = min_conversion_costs[ord(s) - ord("a")][
ord(t) - ord("a")
]
if char_conversion_cost == float("inf"):
return -1 # Conversion not possible
total_cost += char_conversion_cost
return total_cost
def _dijkstra(
self, start_char: int, adjacency_list: List[List[tuple]]
) -> List[int]:
# Priority queue to store characters with their conversion cost, sorted by cost
priority_queue = [(0, start_char)]
# List to store the minimum conversion cost to each character
min_costs = [float("inf")] * 26
while priority_queue:
current_cost, current_char = heapq.heappop(priority_queue)
if min_costs[current_char] != float("inf"):
continue
min_costs[current_char] = current_cost
# Explore all possible conversions from the current character
for target_char, conversion_cost in adjacency_list[current_char]:
new_total_cost = current_cost + conversion_cost
# If we found a cheaper conversion, update its cost
if min_costs[target_char] == float("inf"):
heapq.heappush(
priority_queue, (new_total_cost, target_char)
)
# Return the list of minimum conversion costs from the starting character to all others
return min_costs
Approach 2: Floyd-Warshall Algorithm
class Solution:
def minimumCost(
self,
source: str,
target: str,
original: List[str],
changed: List[str],
cost: List[int],
) -> int:
# Initialize result to store the total minimum cost
total_cost = 0
# Initialize a 2D list to store the minimum transformation cost
# between any two characters
min_cost = [[float("inf")] * 26 for _ in range(26)]
# Fill the initial transformation costs from the given original,
# changed, and cost arrays
for orig, chg, cst in zip(original, changed, cost):
start_char = ord(orig) - ord("a")
end_char = ord(chg) - ord("a")
min_cost[start_char][end_char] = min(
min_cost[start_char][end_char], cst
)
# Use Floyd-Warshall algorithm to find the shortest path between any
# two characters
for k in range(26):
for i in range(26):
for j in range(26):
min_cost[i][j] = min(
min_cost[i][j], min_cost[i][k] + min_cost[k][j]
)
# Calculate the total minimum cost to transform the source string to
# the target string
for src, tgt in zip(source, target):
if src == tgt:
continue
source_char = ord(src) - ord("a")
target_char = ord(tgt) - ord("a")
# If the transformation is not possible, return -1
if min_cost[source_char][target_char] == float("inf"):
return -1
total_cost += min_cost[source_char][target_char]
return total_cost
