You are given two 0-indexed strings source and target, both of length n and consisting of lowercase English letters. You are also given 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].
You start with the string source. In one operation, you can pick a character x from the string and change it to the character y at a cost of z if there exists any index j such that cost[j] == z, original[j] == x, and changed[j] == y.
Return the minimum cost to convert the string source to the string target using any number of operations. If it is impossible to convert source to target, return -1.
Note that there may exist indices i, j such that original[j] == original[i] and changed[j] == changed[i].
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 <= 105source, target consist of lowercase English letters.1 <= cost.length == original.length == changed.length <= 2000original[i], changed[i] are lowercase English letters.1 <= cost[i] <= 106original[i] != changed[i]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.
dijkstra 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.
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.
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.
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.
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.
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.
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.
C++
Java
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).
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.
This Python solution precomputes shortest paths for any character transformation using Floyd-Warshall. We map characters to indices (0 to 25) representing the alphabet.
C++
Java
Time Complexity: O(26^3 + N), Space Complexity: O(26^2).
| Approach | Complexity |
|---|---|
| Graph Based Shortest Path Approach | 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. |
| Dynamic Programming with Floyd-Warshall | 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. |
| Graph-based Approach with Dijkstra's Algorithm | 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). |
| Floyd-Warshall Algorithm for All-Pairs Shortest Path | Time Complexity: O(26^3 + N), Space Complexity: O(26^2). |
Minimum Cost to Cut a Stick - Leetcode 1547 - Python • NeetCodeIO • 16,320 views views
Watch 9 more video solutions →Practice Minimum Cost to Convert String I with our built-in code editor and test cases.
Practice on FleetCode