You are given two 0-indexed strings source and target, both of length n and consisting of lowercase English characters. You are also given two 0-indexed string arrays original and changed, and an integer array cost, where cost[i] represents the cost of converting the string original[i] to the string changed[i].
You start with the string source. In one operation, you can pick a substring x from the string, and change it to y at a cost of z if there exists any index j such that cost[j] == z, original[j] == x, and changed[j] == y. You are allowed to do any number of operations, but any pair of operations must satisfy either of these two conditions:
source[a..b] and source[c..d] with either b < c or d < a. In other words, the indices picked in both operations are disjoint.source[a..b] and source[c..d] with a == c and b == d. In other words, the indices picked in both operations are identical.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 "abcd" to "acbe", do the following operations: - Change substring source[1..1] from "b" to "c" at a cost of 5. - Change substring source[2..2] from "c" to "e" at a cost of 1. - Change substring source[2..2] from "e" to "b" at a cost of 2. - Change substring source[3..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 = "abcdefgh", target = "acdeeghh", original = ["bcd","fgh","thh"], changed = ["cde","thh","ghh"], cost = [1,3,5] Output: 9 Explanation: To convert "abcdefgh" to "acdeeghh", do the following operations: - Change substring source[1..3] from "bcd" to "cde" at a cost of 1. - Change substring source[5..7] from "fgh" to "thh" at a cost of 3. We can do this operation because indices [5,7] are disjoint with indices picked in the first operation. - Change substring source[5..7] from "thh" to "ghh" at a cost of 5. We can do this operation because indices [5,7] are disjoint with indices picked in the first operation, and identical with indices picked in the second operation. The total cost incurred is 1 + 3 + 5 = 9. It can be shown that this is the minimum possible cost.
Example 3:
Input: source = "abcdefgh", target = "addddddd", original = ["bcd","defgh"], changed = ["ddd","ddddd"], cost = [100,1578] Output: -1 Explanation: It is impossible to convert "abcdefgh" to "addddddd". If you select substring source[1..3] as the first operation to change "abcdefgh" to "adddefgh", you cannot select substring source[3..7] as the second operation because it has a common index, 3, with the first operation. If you select substring source[3..7] as the first operation to change "abcdefgh" to "abcddddd", you cannot select substring source[1..3] as the second operation because it has a common index, 3, with the first operation.
Constraints:
1 <= source.length == target.length <= 1000source, target consist only of lowercase English characters.1 <= cost.length == original.length == changed.length <= 1001 <= original[i].length == changed[i].length <= source.lengthoriginal[i], changed[i] consist only of lowercase English characters.original[i] != changed[i]1 <= cost[i] <= 106Problem Overview: You receive two strings source and target plus a list of substring conversions where original[i] can be turned into changed[i] with a cost. Conversions can be chained, and you must transform source into target with the minimum total cost.
Approach 1: Dynamic Programming + Trie + Shortest Path (Time: O(n·L + k^3), Space: O(k^2 + n))
The key challenge is that substring conversions can chain together, meaning converting a → b → c might be cheaper than a direct rule. First treat each unique pattern from original and changed as a node in a graph. Build edges from original[i] to changed[i] with weight cost[i], then run an all‑pairs shortest path algorithm such as Floyd–Warshall to compute the minimum conversion cost between every pair of patterns. Next, store the patterns in a Trie so you can quickly match substrings while scanning the strings. Use dynamic programming where dp[i] represents the minimum cost to convert the first i characters. From each position i, walk both the source and target through the Trie simultaneously to find valid substring pairs and update dp[j]. This combines Dynamic Programming, Trie, and Shortest Path techniques to efficiently evaluate all valid conversions.
Approach 2: DFS with Memoization (Time: O(n·L + states), Space: O(n + recursion))
A top‑down variant treats the problem as a recursive search over the string index. Starting at position i, try every substring conversion that matches the current prefix of source and the corresponding part of target. For each valid segment, recursively compute the cost of converting the remaining suffix. Memoize results for each index so the same suffix is never recomputed. As with the DP approach, shortest conversion costs between patterns must be precomputed using a graph algorithm. This version is often easier to implement in Python but can be slightly slower due to recursion overhead and repeated substring checks.
Recommended for interviews: The bottom‑up dynamic programming approach with Trie matching and precomputed shortest paths is the most robust solution. Interviewers want to see that you model substring transformations as a graph problem and combine it with DP over string positions. Explaining the brute reasoning (trying every substring) shows understanding, while optimizing with Trie lookups and shortest path preprocessing demonstrates strong algorithmic design.
In this approach, we use dynamic programming to solve the problem. We create a DP table where dp[i] represents the minimum cost to transform source[0..i] to target[0..i].
Iterate over each position and evaluate possible transformations using the given substring transformations. If a valid transformation is found that respects the condition, update the DP table with the transformation cost.
The result will be the minimum cost to transform the entire source to target, stored in dp[n-1]. If no valid transformations can achieve this, return -1.
This C solution initializes a DP array and iteratively checks all possible substring transformations at each position in the string. If a valid transformation allows a substring of source to match a part of target, it updates the DP array with the minimum cost.
Time Complexity: O(n * m * k) where n is the length of the source, m is the number of operations, and k is the length of substrings in operations. Space Complexity: O(n) for the dp array.
Use a depth-first search (DFS) approach combined with memoization to explore all possible substring transformations. Start by exploring possible transformations from the beginning of the string, keeping a record of costs incurred so far.
At each step, attempt to match the start of source with each possible original transformation and recur for the remaining part of the string. Use memoization to store results of previously computed subproblems to reduce redundant calculations.
The result will be the minimum cost obtained from all valid transformation paths. Return -1 if a valid transformation path to target doesn't exist.
This Python solution uses DFS with memoization to explore substring transformation paths, tracking minimal costs recursively. It caches results of previously traversed paths to avoid redundant computations, ensuring efficiency.
Python
Time Complexity: Approximately O(n * m), which is less than the full combinatorial exploration due to memoization. Space Complexity: O(n) for storing results of recursion and memoization cache.
According to the problem description, we can consider each string as a node, and the conversion cost between each pair of strings as a directed edge. We first initialize a 26 times 26 two-dimensional array g, where g[i][j] represents the minimum cost of converting string i to string j. Initially, g[i][j] = infty, and if i = j, then g[i][j] = 0. Here, we can use a trie to store the strings in original and changed along with their corresponding integer identifiers.
Next, we use the Floyd algorithm to calculate the minimum cost between any two strings.
Then, we define a function dfs(i) to represent the minimum cost of converting the string source[i..] to the string target[i..]. The answer is dfs(0).
The calculation process of the function dfs(i) is as follows:
i geq |source|, no conversion is needed, return 0.source[i] = target[i], we can skip directly and recursively calculate dfs(i + 1). We can also enumerate the index j in the range [i, |source|), if source[i..j] and target[i..j] are both in the trie, and their corresponding integer identifiers x and y are both greater than or equal to 0, then we can add dfs(j + 1) and g[x][y] to get the cost of one conversion scheme, and we take the minimum value among all schemes.In summary, we can get:
$
dfs(i) = \begin{cases}
0, & i geq |source| \
dfs(i + 1), & source[i] = target[i] \
min_{i leq j < |source|} { dfs(j + 1) + g[x][y] }, & otherwise
\end{cases}
Where x and y are the integer identifiers of source[i..j] and target[i..j] in the trie, respectively.
To avoid repeated calculations, we can use memoization search.
The time complexity is O(m^3 + n^2 + m times n), and the space complexity is O(m^2 + m times n + n). Where m and n$ are the lengths of the arrays original and source, respectively.
| Approach | Complexity |
|---|---|
| Approach 1: Dynamic Programming | Time Complexity: O(n * m * k) where n is the length of the source, m is the number of operations, and k is the length of substrings in operations. Space Complexity: O(n) for the dp array. |
| Approach 2: DFS with Memoization | Time Complexity: Approximately O(n * m), which is less than the full combinatorial exploration due to memoization. Space Complexity: O(n) for storing results of recursion and memoization cache. |
| Trie + Floyd Algorithm + Memoization Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming + Trie + Shortest Path | O(n·L + k^3) | O(k^2 + n) | Best general solution when many substring rules exist and chaining conversions is allowed |
| DFS with Memoization | O(n·L + states) | O(n) | Simpler top‑down implementation, good for Python when recursion depth is manageable |
Minimum Cost to Convert String II | Simplified Explanation | Intuition | Leetcode 2977 | MIK • codestorywithMIK • 7,705 views views
Watch 9 more video solutions →Practice Minimum Cost to Convert String II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor