Sponsored
Sponsored
In this approach, we can model the problem as a graph where each character is a node, and directed edges with weights indicate a transformation from one character to another. The edges represent 'original to changed' characters with the given cost. To achieve the transformation from source to target, we need to find the minimum cost path for each position in the source string.
We can utilize Dijkstra's algorithm to find the shortest path from each character in source[i] to target[i] based on the transformation rules. For each character transformation, attempt to find the minimum cost path to transform each character accordingly.
Time Complexity: O(n * (V + E) log V) where V is the number of unique characters (vertices) and E is the number of transformation rules (edges).Space Complexity: O(V + E) for graph representation and auxiliary data structures.
1import heapq
2from collections import defaultdict
3
4def minCostToConvert(source, target, original, changed, cost):
5 n = len(source)
6 graph = defaultdict(list)
7
8 # Building the graph
9 for o, c, w in zip(original, changed, cost):
10 graph[o].append((c, w))
11
12 def dijkstra(start, end):
13 pq = [(0, start)] # (cost, node)
14 visited = set()
15
16 while pq:
17 curr_cost, u = heapq.heappop(pq)
18 if u == end:
19 return curr_cost
20 if u in visited:
21 continue
22 visited.add(u)
23 for v, weight in graph[u]:
24 if v not in visited:
25 heapq.heappush(pq, (curr_cost + weight, v))
26 return float('inf')
27
28 total_cost = 0
29
30 for s, t in zip(source, target):
31 if s == t:
32 continue
33 min_cost = dijkstra(s, t)
34 if min_cost == float('inf'):
35 return -1
36 total_cost += min_cost
37
38 return total_cost
39dijkstra function is used to find the shortest transformation cost from one character to another. It utilizes a min-heap priority queue to efficiently extract the minimum path cost fascinatingly similar to Dijkstra's algorithm for shortest path in graphs. For each character of the source and target, it calculates the minimum transformation cost.
This approach involves using the Floyd-Warshall algorithm to pre-compute the shortest transformation cost between any two characters. Consider this as an all-pairs shortest path where each character is a node in the graph, and transformations provide weighted edges. First, apply Floyd-Warshall to compute minimum transformation costs between characters. Then, for each character in the source string, find the transformation cost to match the target using pre-computed values.
Time Complexity: O(n + V^3), where n is the string length and V is the number of unique characters (26 for lowercase alphabets). Space Complexity: O(V^2) for storing the distance transformation table.
1def minCostToConvert(source, target, original, changed, cost):
2
The primary idea is to use a graph where each letter is a node, and transformations are directed edges with weights (costs). We can use Dijkstra's algorithm to find the shortest path (minimum cost) to convert each character from source to the corresponding character in target.
Time Complexity: O(M log C) per pair of letters to transform, where M is the number of edges (transformations) and C is the total graph nodes (the alphabet size). Space Complexity: O(C + M).
1import heapq
2from collections import
This approach utilizes the Floyd-Warshall algorithm to precompute the minimum cost from every character to every other character. This is helpful as we need to transform multiple characters efficiently.
Time Complexity: O(26^3 + N), Space Complexity: O(26^2).
1#include <bits/stdc++.h>
2using namespace std;
3
4int minCostToConvert(string source, string target, vector<char>& original, vector<char>& changed, vector<int>& cost) {
const int INF = 1e9;
vector<vector<int>> dist(26, vector<int>(26, INF));
for (int i = 0; i < 26; ++i) dist[i][i] = 0;
for (size_t i = 0; i < original.size(); ++i) {
int u = original[i] - 'a', v = changed[i] - 'a';
dist[u][v] = min(dist[u][v], cost[i]);
}
for (int k = 0; k < 26; ++k)
for (int i = 0; i < 26; ++i)
for (int j = 0; j < 26; ++j)
if (dist[i][k] < INF && dist[k][j] < INF)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
int total_cost = 0;
for (size_t i = 0; i < source.size(); ++i) {
if (source[i] == target[i]) continue;
int cost_to_transform = dist[source[i] - 'a'][target[i] - 'a'];
if (cost_to_transform == INF) return -1;
total_cost += cost_to_transform;
}
return total_cost;
}The Dynamic Programming table dp is filled using the character to character transformation cost. Initial direct transformation costs are added using the problem's input, followed by updates using the Floyd-Warshall algorithm to include indirect transformations for building comprehensive paths.
The Python solution uses the Dijkstra's algorithm to find the minimum cost path between each letter that needs transformation. We maintain a priority queue to efficiently extract the minimum cost transformation at each step.
The C++ solution applies Floyd-Warshall to precompute transformation costs, allowing constant time retrieval for any needed transformation between characters.