Converting one string into another often feels like a simple find and replace task. However, when every individual character change has a specific price tag, and you can take multiple "detours" through other characters to save money, the problem transforms into a fascinating pathfinding challenge.
You're given:
- Two strings,
sourceandtarget, of the same length. - A set of allowed character transformations (e.g., change 'a' to 'b') and their associated costs.
- The ability to use multiple steps to reach a target character (e.g., 'a' to 'c' to 'b').
Your goal:
- Calculate the minimum total cost to transform every character in
sourceto the corresponding character intarget. - Return -1 if any character in the
sourcecannot be transformed into the requiredtargetcharacter.
Examples:
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: To convert the string "abcd" to string "acbe":
- Change value at index 1 from 'b' to 'c' at a cost of 5.
- Change value at index 2 from 'c' to 'e' at a cost of 1.
- Change value at index 2 from 'e' to 'b' at a cost of 2.
- Change value at index 3 from 'd' to 'e' at a cost of 20. The total cost incurred is 5 + 1 + 2 + 20 = 28. It can be shown that this is the minimum possible cost.
Example 2:
Input: source = "aaaa", target = "bbbb", original = ["a","c"], changed = ["c","b"], cost = [1,2]
Output: 12
Explanation: To change the character 'a' to 'b' change the character 'a' to 'c' at a cost of 1, followed by changing the character 'c' to 'b' at a cost of 2, for a total cost of 1 + 2 = 3. To change all occurrences of 'a' to 'b', a total cost of 3 * 4 = 12 is incurred.
Example 3:
Input: source = "abcd", target = "abce", original = ["a"], changed = ["e"], cost = [10000]
Output: -1
Explanation: It is impossible to convert source to target because the value at index 3 cannot be changed from 'd' to 'e'.
Constraints:
- 1 <= source.length == target.length <= 105
- source, 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] <= 106
- original[i] != changed[i]
Intuition: Thinking in Graphs
Think of the English alphabet as 26 distinct cities. Every transformation rule given in the input is a one-way road between these cities with a specific toll (the cost). Our task is to find the cheapest route from "City A" to "City B" for every character pair in our strings.
Since we only have 26 possible characters, we can pre-calculate the shortest path between every possible pair of letters. Even if the input gives us a direct path from 'a' to 'b' costing 10, there might be a cheaper way: 'a' to 'c' (cost 2) and then 'c' to 'b' (cost 3), totaling only 5.
We use the Floyd-Warshall Algorithm to solve this. It systematically checks if passing through an intermediate letter 'k' provides a cheaper path between letters 'i' and 'j'. Once we have this 26x26 matrix of minimum costs, we simply iterate through our strings and sum up the values.
Walkthrough: Understanding the Examples
Example 1: source = "abcd", target = "acbe"
- Index 0: 'a' to 'a'. Cost is 0.
- Index 1: 'b' to 'c'. The direct cost is 5.
- Index 2: 'c' to 'b'. Direct cost is not available, but we can go 'c' to 'e' (1) and 'e' to 'b' (2). Total cost is 3.
- Index 3: 'd' to 'e'. Direct cost is 20.
- Total: .
Example 2: source = "aaaa", target = "bbbb"
- Rules: 'a' to 'c' (1), 'c' to 'b' (2).
- To get from 'a' to 'b', we must go through 'c'. Cost per character is .
- Since there are 4 characters, total cost is .
C++ Solution
class Solution {
public:
long long minimumCost(string source, string target, vector<char>& original, vector<char>& changed, vector<int>& cost) {
const long long INF = 1e14;
// Initialize a 26x26 matrix with a very large value
vector<vector<long long>> minCost(26, vector<long long>(26, INF));
// Cost to stay the same is zero
for(int i = 0; i < 26; i++) minCost[i][i] = 0;
// Fill initial transformation costs
for(int i = 0; i < original.size(); i++) {
int u = original[i] - 'a';
int v = changed[i] - 'a';
minCost[u][v] = min(minCost[u][v], (long long)cost[i]);
}
// Floyd-Warshall: Find shortest paths between all pairs
for(int k = 0; k < 26; k++) {
for(int i = 0; i < 26; i++) {
for(int j = 0; j < 26; j++) {
if(minCost[i][k] != INF && minCost[k][j] != INF) {
minCost[i][j] = min(minCost[i][j], minCost[i][k] + minCost[k][j]);
}
}
}
}
long long totalCost = 0;
for(int i = 0; i < source.size(); i++) {
int u = source[i] - 'a';
int v = target[i] - 'a';
if(minCost[u][v] == INF) return -1;
totalCost += minCost[u][v];
}
return totalCost;
}
};
Python Solution
class Solution:
def minimumCost(self, source: str, target: str, original: list[str], changed: list[str], cost: list[int]) -> int:
INF = float('inf')
# Create a 26x26 grid initialized to infinity
dist = [[INF] * 26 for _ in range(26)]
for i in range(26):
dist[i][i] = 0
# Map characters to 0-25 and fill initial costs
for o, c, z in zip(original, changed, cost):
u, v = ord(o) - ord('a'), ord(c) - ord('a')
dist[u][v] = min(dist[u][v], z)
# Floyd-Warshall Algorithm
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]
total_cost = 0
for s, t in zip(source, target):
u, v = ord(s) - ord('a'), ord(t) - ord('a')
if dist[u][v] == INF:
return -1
total_cost += dist[u][v]
return int(total_cost)
JavaScript Solution
/**
* @param {string} source
* @param {string} target
* @param {character[]} original
* @param {character[]} changed
* @param {number[]} cost
* @return {number}
*/
var minimumCost = function(source, target, original, changed, cost) {
const INF = Number.MAX_SAFE_INTEGER;
const dist = Array.from({ length: 26 }, () => Array(26).fill(INF));
for (let i = 0; i < 26; i++) dist[i][i] = 0;
for (let i = 0; i < original.length; i++) {
const u = original[i].charCodeAt(0) - 97;
const v = changed[i].charCodeAt(0) - 97;
dist[u][v] = Math.min(dist[u][v], cost[i]);
}
// Floyd-Warshall to find all-pairs shortest paths
for (let k = 0; k < 26; k++) {
for (let i = 0; i < 26; i++) {
for (let j = 0; j < 26; j++) {
if (dist[i][k] !== INF && dist[k][j] !== INF) {
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
let totalCost = 0;
for (let i = 0; i < source.length; i++) {
const u = source.charCodeAt(i) - 97;
const v = target.charCodeAt(i) - 97;
if (dist[u][v] === INF) return -1;
totalCost += dist[u][v];
}
return totalCost;
};
Key Takeaways
- All-Pairs Shortest Path: When you need to find the shortest path between all possible nodes in a small graph (like the 26 letters of the alphabet), Floyd-Warshall is your best friend.
- Graph Modeling: Many problems that don't look like "maps" can be treated as graphs if they involve transitions between states with specific costs.
- Handling Infinity: When calculating minimums, initialize your values to a sufficiently large number to represent "impossible" paths, but ensure it doesn't cause overflow in your language.
Final Thoughts
This problem is a classic example of why recognizing patterns is more important than memorizing code. In a real-world software system, this logic is used in things like network routing protocols or recommendation engines where we need to find the most efficient connection between two points through various intermediaries. Mastering this ensures you can handle optimization tasks where the best path isn't always the most obvious one.
Top comments (0)