Watch 4 video solutions for Minimum Cost to Convert String III, a hard level problem. This walkthrough by DSA with Kumar K has 197 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two strings, source and target.
You are also given a 2D string array rules, where rules[i] = [patterni, replacementi], and an integer array costs, where costs[i] is the base cost of applying rules[i]. Both arrays have the same length. Additionally, patterni and replacementi have the same length.
You may apply any rule any number of times. Each rule application works as follows:
l such that the range of positions from l to l + patterni.length - 1 exists in the current string and none of these positions has been used in a previous rule application.j, the character patterni[j] must either be equal to the current character at position l + j, or be '*'.replacementi. The replacement is used exactly as given and does not contain wildcards.costs[i] plus the number of '*' characters in patterni.Since every patterni and replacementi have the same length, character positions are preserved after every rule application.
Return the minimum total cost required to transform source into target. If it is impossible, return -1.
Example 1:
Input: source = "hello", target = "world", rules = [["he","wo"],["llo","rld"]], costs = [3,4]
Output: 7
Explanation:
rules[0] to replace "he" with "wo" at cost 3, so the string becomes "wollo".rules[1] to replace "llo" with "rld" at cost 4, so the string becomes "world".3 + 4 = 7.Example 2:
Input: source = "cat", target = "dog", rules = [["c*t","dog"]], costs = [2]
Output: 3
Explanation:
rules[0] to replace "cat" with "dog". The wildcard '*' matches 'a', adding 1 to the base cost 2.2 + 1 = 3.Example 3:
Input: source = "test", target = "next", rules = [["*e*t","next"]], costs = [4]
Output: 6
Explanation:
rules[0] to replace "test" with "next". The first wildcard matches 't' and the second wildcard matches 's', adding 2 to the base cost 4.4 + 2 = 6.Example 4:
Input: source = "ab", target = "bc", rules = [["a*","bd"]], costs = [9]
Output: -1
Explanation:
No sequence of rule applications can transform source into target, so the answer is -1.
Constraints:
1 <= source.length == target.length <= 5000source and target consist of lowercase English letters.1 <= rules.length == costs.length <= 200rules[i] = [patterni, replacementi]1 <= patterni.length == replacementi.length <= 20patterni contains at least one lowercase English letter and at most 5 '*' characters.replacementi contains only lowercase English letters.1 <= costs[i] <= 1000Problem Overview: You need to transform one string into another while minimizing the total conversion cost. Each operation changes characters or substrings based on allowed transformations, so the core challenge is finding the cheapest valid sequence of conversions.
Approach 1: Exhaustive DFS / Backtracking (Exponential Time, O(n) Space)
The brute force solution tries every possible conversion sequence recursively. For each position, you iterate through all allowed transformations and continue searching until the target string is formed. This approach helps you reason about the state transitions, but overlapping subproblems make it impractical for large inputs. Time complexity grows exponentially because the same partial conversions are recomputed many times.
Approach 2: Dynamic Programming with Memoization (O(n * m) to O(n * m^2), O(n * m) Space)
A top-down DP caches the minimum cost for converting suffixes or intermediate states. Instead of recomputing paths, you perform hash lookups in the memo table and reuse previously solved states. This works well when the number of unique transformation states is manageable. Problems involving repeated substring decisions often combine dynamic programming with indexed transitions to reduce redundant work.
Approach 3: Graph Shortest Paths + DP (Optimal)
The optimal solution models transformations as a weighted graph where nodes represent characters or substrings and edges represent conversion costs. You first compute minimum conversion costs between all reachable states using algorithms like Floyd-Warshall or Dijkstra. After preprocessing, iterate through the source string and accumulate the cheapest valid transitions with DP. This separates path optimization from string traversal and avoids repeated shortest-path computation. Time complexity depends on the graph size, commonly O(k^3 + n) with Floyd-Warshall preprocessing, while space complexity is typically O(k^2).
Approach 4: Trie + Shortest Path Optimization
If transformations involve variable-length substrings, a trie can reduce matching overhead during traversal. You scan the string once, walk trie edges for candidate replacements, and combine the result with precomputed graph distances. This technique is useful when the dictionary of conversions is large and substring matching becomes the bottleneck. Problems combining graphs, shortest paths, and trie traversal frequently appear in hard interview rounds.
Recommended for interviews: Interviewers usually expect the graph shortest-path preprocessing combined with DP. The brute force approach shows you understand the state space, but the optimized graph-based solution demonstrates algorithmic maturity, especially when you explain why preprocessing eliminates repeated conversion cost calculations.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS / Backtracking | Exponential | O(n) | Small inputs or validating state transitions |
| Memoized Dynamic Programming | O(n * m) to O(n * m^2) | O(n * m) | When overlapping subproblems dominate runtime |
| Graph Shortest Paths + DP | O(k^3 + n) | O(k^2) | General optimal solution for weighted transformations |
| Trie + Graph Optimization | O(totalTransitions + n) | O(trieSize + k^2) | Large substring dictionaries and repeated prefix matching |