Is Minimum Cost to Convert String III easy or hard?

Minimum Cost to Convert String III is classified as a Hard problem because it combines multiple advanced concepts. You need to coordinate shortest-path algorithms, dynamic programming, and efficient state transitions under strict complexity constraints.

Minimum Cost to Convert String III Python/Java solution

Python solutions usually rely on dictionaries, memoization, and Floyd-Warshall preprocessing because matrix operations are concise to implement. Java solutions often use arrays and adjacency matrices for faster constant factors and predictable memory usage.

How to solve Minimum Cost to Convert String III in O(n)?

The string traversal itself can run in O(n) after preprocessing transformation costs. The key idea is separating shortest-path computation from the actual conversion process, so each character or substring lookup becomes constant or near-constant time during iteration.

What is the best approach for Minimum Cost to Convert String III?

The strongest approach combines shortest-path preprocessing with dynamic programming. You compute the cheapest conversion cost between all valid states first, then iterate through the string while applying those precomputed costs. This avoids recomputing expensive transformations repeatedly.

Is Minimum Cost to Convert String III asked at Google/Amazon/Meta?

Hard graph and dynamic programming problems with weighted transformations are common in Google and Meta interview loops. Variants involving shortest paths, memoization, and string conversion also appear in Amazon online assessments and senior-level coding rounds.

What data structure is used in Minimum Cost to Convert String III?

The solution typically uses adjacency matrices or adjacency lists for graph representation, along with DP tables or hash maps for memoization. Some optimized solutions also use tries to match substrings efficiently during traversal.

What is the time complexity of Minimum Cost to Convert String III?

The optimal complexity is commonly O(k^3 + n), where k is the number of distinct transformation states and n is the string length. Floyd-Warshall preprocessing handles all-pairs conversion costs, while the final DP or traversal runs linearly across the string.

Description Hints 5 Video 27:37

3995. Minimum Cost to Convert String III

Hard55.6% acceptance

You are given two strings, source and target.

You are also given a 2D string array rules, where rules[i] = [pattern_i, replacement_i], and an integer array costs, where costs[i] is the base cost of applying rules[i]. Both arrays have the same length. Additionally, pattern_i and replacement_i have the same length.

You may apply any rule any number of times. Each rule application works as follows:

Choose an index l such that the range of positions from l to l + pattern_i.length - 1 exists in the current string and none of these positions has been used in a previous rule application.
For each index j, the character pattern_i[j] must either be equal to the current character at position l + j, or be '*'.
Replace the characters in this range with replacement_i. The replacement is used exactly as given and does not contain wildcards.
The cost of this rule application is costs[i] plus the number of '*' characters in pattern_i.
Once a character position has been used in a rule application, it cannot be used in any later rule application.

Since every pattern_i and replacement_i 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:

Apply rules[0] to replace "he" with "wo" at cost 3, so the string becomes "wollo".
Apply rules[1] to replace "llo" with "rld" at cost 4, so the string becomes "world".
The total cost is 3 + 4 = 7.

Example 2:

Input: source = "cat", target = "dog", rules = [["c*t","dog"]], costs = [2]

Output: 3

Explanation:

Apply rules[0] to replace "cat" with "dog". The wildcard '*' matches 'a', adding 1 to the base cost 2.
The total cost is 2 + 1 = 3.

Example 3:

Input: source = "test", target = "next", rules = [["*e*t","next"]], costs = [4]

Output: 6

Explanation:

Apply 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.
The total cost is 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 <= 5000
source and target consist of lowercase English letters.
1 <= rules.length == costs.length <= 200
rules[i] = [pattern_i, replacement_i]
1 <= pattern_i.length == replacement_i.length <= 20
pattern_i contains at least one lowercase English letter and at most 5 '*' characters.
replacement_i contains only lowercase English letters.
1 <= costs[i] <= 1000

Topics

Hints open one at a time

Hint 1

Because used ranges cannot overlap and all replacements preserve length, each position is either left unchanged or belongs to exactly one applied rule.

Hint 2

Use dynamic programming over prefixes. Let dp[i] be the minimum cost to transform the first i characters of source into the first i characters of target.

Hint 3

If source[i] == target[i], you may leave position i unchanged and update dp[i + 1].

Hint 4

For each rule starting at position i, check whether its pattern matches source[i..i + len - 1] using '*' as a wildcard, and whether its replacement equals target[i..i + len - 1].

Hint 5

If both checks pass, update dp[i + len] using the rule cost plus the number of '*' characters in its pattern.

LanguageLoading editor…

1class Solution:
2    def minCost(self, source: str, target: str, rules: list[list[str]], costs: list[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3Case 4

Input

"hello"
"world"
[["he","wo"],["llo","rld"]]
[3,4]

Input

"cat"
"dog"
[["c*t","dog"]]
[2]

Input

"test"
"next"
[["*e*t","next"]]
[4]

Input

"ab"
"bc"
[["a*","bd"]]
[9]

Your code is saved on this device.